Merge sort is a divide and conquer algorithm that works as follows..
- If the length of the given list is more than 1, divide it into n sublists using recursion, each containing 1 element because a list containing 1 element is always sorted.
- Again using recursion, repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. The final list will be the sorted list.
The python code for the merge sort is as follows…
def merge_list(s,l1,l2): i = 0 j = 0 k = 0 # this loop will make sure one of the lists reaches to the end and then # subsequent while loop will just append the remaining elements from # the other list while (i < len(l1) and j < len(l2)): if (l1[i] < l2[j]): s[k] = l1[i] # s is the sorted list i = i+1 else: s[k] = l2[j] j = j+1 k = k+1 # append the remaining elements of the list l1 while (i < len(l1)): s[k] = l1[i] i = i+1 k=k+1 # append the remaining elements of the list l2 while (j < len(l2)): s[k] = l2[j] j = j+1 k=k+1 return s def merge_sort(a): n = len(a) if (n == 1): return a else: mid = n//2 # create two sublists l1 = a[:mid] l2 = a[mid:] merge_sort(l1) merge_sort(l2) sorted_list = merge_list(a,l1,l2) return sorted_list l = [13,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] final = merge_sort(l) print "sorted list is ",final
The output of the above program looks like this…
sorted list is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 18]