My quest for sorting algorithms has introduced me to an interesting algorithm, Merge Sort. This one actually works better than other sorting algorithms (discussed so far). Someone really gave it some thought, that is obvious from the working of this algorithm. Despite appearing more complicated, Merge Sort has average time performance of
ϴ( n log(n) ).
Unlike those we have seen so far, this one doesn’t require iteration over all the values followed by a series of comparisons and swaps. Merge Sort divides a sorting problem into small sorting problems and then deals with them one-by-one. As all these smaller problems are sorting problems, we can have them solved by following steps over and again. Here, recursion comes in handy.
Merge Sort goes by making groups of data, and then splitting those groups into further groups half their size. This goes on until the number of groups match the number of origin data elements, each group consisting of one distinct value.
Once we hit the ground, merge sort start sorting each group, and combining groups such that they form a sorted group. This is done be comparing the entries of both groups which are to be combined, and deciding which must be placed ahead of the other. Just like the splitting part, this goes on until there is only one group left, which is in fact our list of sorted data.
Merge Sort algorithm has two parts. One part deals with splitting data and calling on them the second part, sort and merge.
The function given below merges any two given groups by comparing the heads of both groups and merging them by keeping order.
def merge(first, second): temp =  # temporary list to help merging while( first and second ): #while non-empty, when they are empty it means there is nothing to compare if first > second: temp.append( second.pop(0) ) # removing and adding to temp else: temp.append( first.pop(0) ) # removing and adding to temp '''when one group is empty, we the copy the other one as is''' # copying to temp while( first ): temp.append( first.pop(0) ) # removing and adding to temp while( second ): temp.append( second.pop(0) ) # removing and adding to temp return temp # return a merged sorted list
merge is called from the main function where the data is split into to parts. The splitting is carried out recursively.
def merge_sort( myList ): n = len(myList) # size if n is 1: return myList # splitting from middle first = myList[:n//2] second = myList[n//2:] # recursive magic first = merge_sort( first ) second = merge_sort( second ) return merge(first, second)