Mergesort

https://www.dot.state.mn.us/zippermerge/images/zippermergecrop.png

Have u seen merging of traffic from two lanes into one?  You may understand that in principle, cars on both lanes are supposed to interleave in an alternate manner into the single lane, but in reality, likely the more aggressive, impatient drivers will get to go first into that lane. Well, that's the idea in mergesort. You have 2 sorted lists, and you are to move them all into a single sorted list. Frontmost elements from both lists are compared, and the 'stronger' one (however you define that) go into the single list.

Here's a trivial example. Suppose you have 2 lists, where in each list, you have just a single person. You want to move them both into a single list, sorted by height. It's simple - simply check who is taller; move that guy first into the single list.

For example, the guy on the left is shorter, so he goes in first.

followed by the taller guy in the other list.

Now consider the case where each list contains 2 guys in ascending order. Again, we compare the frontmost (or leftmost) guys from both lists. The sorter one goes first.

The frontmost guy on the right list gets to go first of course. Now the next guy in the right list become frontmost, and he will be compared with the current frontmost guy in the left list.

The guy in the left list gets to go in next. And we continue the comparison.

The guy in the left list goes next.

We then clear up the list on the right - move in the remaining guy, and we have a family.

Hence, that's the key idea in mergesort - take 2 sorted list, simply build a single sorted list by taking the shorter of the frontmost elements in both lists. In Python, this logic translates as follows:

        i=0  # index to the current frontmost element in left list
        j=0  # index to the current frontmost element in right list
        k=0 # index to current position in output list
     
        # compare the frontmost elements in left and right list
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]          # add the frontmost element from left list
                i=i+1                              # index to a new frontmost element  in left list
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1                  # update index to current position in output list


And suppose we are done processing the right list, but there are still elements left in the left list. We need to simply funnel those remaining elements into the output list, one after another.  No comparison or check is needed as those remaining elements are no smaller than any element in the output list. The code looks as follows:

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

And the same logic applies should there be elements remaining in the right list:

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

The above code can be contained into a single function, with the header say as follows:

def mergeSort(lefthalf, righthalf):

Mergesort with a Single List


In real application, of course, we do not regularly get 2 sorted lists. Likely, we get a single list of random items and asked to do a sort on it. How do we do a mergesort with a single list? Consider the following:

There is only a single list, but we can think of it as 2 sublists:

And for each of the sublists, we can do further subdivision, producing more sublists:

Eventually, we have sublists splitting into smaller sublists comprising of only a single element each, and eventually no more recursive subdivision can be done. We now can start merging sublists in a bottom up manner.

Note how the single-element sublists at the bottom of the tree get to be merged into a single sorted sublist 1 level above:

Continue the bottom-up merging:

Eventually you have 2 sublists to be merged, as show below:

Merging those 2, we get the overall sorted list, as follows:

The above recursive logic can of course be implemented as a recursive function. Assuming a split down the middle at each subdivision, we have the following function:

def mergeSort(alist):

    if len(alist)>1:
        mid = len(alist)//2                 # split at this index
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)               # recursive call
        mergeSort(righthalf)

        alist = mergeSort(lefthalf, righthalf)   # this merge two lists into a single sorted list

    return alist;