For marketers
who love technology
Home » , » Sorting algorithms - merge sort source code in python

Sorting algorithms - merge sort source code in python

Merge sort algorithm diagram.svg
Merge sort algorithm diagram (Photo credit: Wikipedia)

How to code the merge sort algorithm in Python 

You can find below my implementation in python of the famous merge sort algorithm. Merge sort is one of the best sort algorithms (complexity in O(n log n)):


import math
to_be_sorted=[5,2,3,4,2,5,8,9,12,-1,6]

def merge_sort(my_list, order="increasing"):
    """
    Sorts a list in the specified order, using merge sort algorithm
    """
    sorted_list =[0]*len(my_list)
    # exceptions
    if  order not in ["increasing"]:
        raise ValueError("order should be specified")
    if len(my_list)<=1:
        return my_list
    # ending condition
    if len(my_list)==2:
        if my_list[0] <= my_list[1]:
            sorted_list= my_list
        else:
            sorted_list=[my_list[1],my_list[0]]
        return sorted_list
    # "normal" case
    else:
        limit = math.floor(len(my_list)/2)
        # sort left and right parts
        left = merge_sort(my_list[0:limit]) 
        right = merge_sort(my_list[limit+1:])        
        id_left, id_right=0 ,0
        while id_left<=len(left)-1 and id_right<=len(right)-1 :
            # merge left and right
            # example : [2,8] [6,9,11]
            # first compare 2 and 6. take 2 => [8] [6,9,11]
            # compare 8 and 6, take 6 => |8] [9,11]
            # compare 8 and 9, take 8=> [] [9,11]          
            if left[id_left] < right[id_right]:
                sorted_list[id_left+id_right] = left[id_left]
                id_left +=1
            else:
                sorted_list[id_left+id_right] = right[id_right]
                id_right +=1
        # at this stage either left or right is empty, and the other list is sorted
        # so just append the non empty list to the sorted result
        # take the remainder [9,11] of right => [][]          
        sorted_list[id_left+id_right:] = left[id_left:] + right[id_right:]
        return sorted_list 

Sorting algorithms for interviews

If you are studying merge sort, there is a good chance you are preparing for an interview. Am I right? If so, I strongly recommend you to read the two following books: they are the best preparation material a computer scientist can get her hands on when preparing for interviews!


  

The second book, "Cracking the PM interview" is useful for Technical Program Managers. It focuses more on Product Manager roles, it is nevertheless the best resource I have found to date to prepare for PM roles at GAFAs.


Good luck with your interview, and please share this article if you found it helpful. It will help us rank better in search engines. Thanks a million times! 

SHARE

About Gilles

0 comments :

Post a Comment