python - Explanation of Merge Sort for Dummies

Question

I found this code online:

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

It works 100% when I run it. I just do not really get how the merge sort works or how the recursive function is able to properly order both a left and a right.

Answer 1

I believe that the key to understanding merge sort is understanding the following principle -- I'll call it the merge principle:

Given two separate lists A and B ordered from least to greatest, construct a list C by repeatedly comparing the least value of A to the least value of B, removing the lesser value, and appending it onto C. When one list is exhausted, append the remaining items in the other list onto C in order. The list C is then also a sorted list.

If you work this out by hand a few times, you'll see that it's correct. For example:

A = 1, 3
B = 2, 4
C = 
min(min(A), min(B)) = 1

A = 3
B = 2, 4
C = 1
min(min(A), min(B)) = 2

A = 3
B = 4
C = 1, 2
min(min(A), min(B)) = 3

A = 
B = 4
C = 1, 2, 3

Now A is exhausted, so extend C with the remaining values from B:

C = 1, 2, 3, 4

The merge principle is also easy to prove. The minimum value of A is less than all other values of A, and the minimum value of B is less than all other values of B. If the minimum value of A is less than the minimum value of B, then it must also be less than all values of B. Therefore it is less than all values of A and all values of B.

So as long as you keep appending the value that meets those criteria to C, you get a sorted list. This is what the merge function above does.

Now, given this principle, it's very easy to understand a sorting technique that sorts a list by dividing it up into smaller lists, sorting those lists, and then merging those sorted lists together. The merge_sort function is simply a function that divides a list in half, sorts those two lists, and then merges those two lists together in the manner described above.

The only catch is that because it is recursive, when it sorts the two sub-lists, it does so by passing them to itself! If you're having difficulty understanding the recursion here, I would suggest studying simpler problems first. But if you get the basics of recursion already, then all you have to realize is that a one-item list is already sorted. Merging two one-item lists generates a sorted two-item list; merging two two-item lists generates a sorted four-item list; and so on.