We want to sort an array with n elements. Merge-sort does this by breaking up the array into two-halves, sorting them separately and then combining the results.

Merge-sort Algorithm

The first 2.5 minutes of the video above explain the merge-sort algorithm. The next 3 minutes (optional) compare merge-sort and quick-sort in one case where quick-sort's pivot choices get lucky, and another where quick-sort gets unlucky.

GIF animation of Merge-sort

Algorithm Steps

define mergesort(x):
    recursively sort first-half of x
    recursively sort second-half of x
    merge sorted halfs into single sorted array

Run-time analysis

The easiest way to understand the run-time complexity of merge-sort is to look at the recursion graph. There are O(log n) layers in the tree, and each layer is size O(n). Hence, the total algorithm is O(n log n).

Code (almost python)

define mergesort(x):
    """ Sort array using merge sort algorithm """
 
    # base case 
    if length(x) <= 1: return x 
 
    # split from middle. mergesort each half. then merge
    middle = length(x)/2
    a = mergesort(x[:middle])
    b = mergesort(x[middle:])
    return merge(a, b)
 
define merge(a, b):
    """ merge arrays a and b """
 
    c = list()
    while not empty(a) or not empty(b):
        # add smaller element to c and remove from original array
        # (handle boundary cases of a / b being empty)
        if empty(a) or (not empty(b) and a[0] <= b[0]): 
            c.append(a[0])
            a.pop()
        else:
            c.append(b[0])
            b.pop()
    return c
 

References

1. Merge-sort | Wikipedia
2. Merge Sort Algorithm