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

You can have a good visualization on how the merge sort works here:

http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html

I hope it helps.

Answer 2

A picture is worth a thousand words, and an animation worth 10,000.

Checkout the following animation taken from Wikipedia that will help you visualize how the merge sort algorithm actually works.

Detailed animation with explanation for each step in the sorting process for the inquisitive ones.

Another interesting animation of various types of sorting algorithms.