|Merge sort algorithm diagram (Photo credit: Wikipedia)|
How to code the merge sort algorithm in PythonYou 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 =*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 <= my_list: sorted_list= my_list else: sorted_list=[my_list,my_list] 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 =>  [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 interviewsIf 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!