- a developer's blog

Merge Sort Algorithm in Python

Merge sort algorithm breaks a larger list into several smaller lists, sorts them individually and incrementally merges them back to return the sorted list.

For instance, let us say we need to sort a list of 500 elements. An algorithm implementation like bubble sort would take O(n^2) number of steps, which is about 250,000 steps. Merge sort would rather split this list into 50 lists each with 10 items. Now it would 100 steps to sort each of these list adding up to (50000)500*100 steps for sorting each of these individual lists. After each list has sorted, the lists are merged back together which would take approximately 500 steps adding up to a total of 50000 + 500 steps or 50500 steps which is a vast improvement over 250,000 steps in the bubble algorithm. This is the essence of how merge sort works.

Now for the python code implementation:

def merge_sort(lst): 
   mid = len(lst)//2 
   lft, rght = seq[:mid], seq[mid:] 
   if len(lft) > 1: lft = merge_sort(lft) 
   if len(rght) > 1: rgt = merge_sort(rght) 
   sorted_list = [] 
   while lft and rght: 
     if lft[-1] >= rght[-1]: 
   return (lft or rght) +    sorted_list