Posts /

Algo #4: Merge Sort

4 mins read ●
Twitter Facebook Google+
03 Sep 2017

Merge Sort

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) ).

Idea

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.

Working

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 Animation  
Visual demonstration of Merge Sort.

Code

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.

Important!!!
It should be noted that this function does not actually sort the data, it merges two groups by looking at their entries one-by-one. The data is sorted by recursion on this part. The smaller groups are already sorted when they are given for merging, and this goes on. It is better understood by an example given in this notebook.
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[0] > second[0]:
            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

The 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)

To see the results of this function, open link. In case of any errors, open an issue in 100 Algorithms repo OR comment below..


You may also like...


Twitter Facebook Google+