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
An animation of the merge sort algorithm. First recursively split the array into smaller parts. Then repeatedly merge the small sorted arrays into a combined sorted array. [1]
Algorithm Steps
define mergesort(x):recursively sort first-half of xrecursively sort second-half of xmerge 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).
Diagram of recursion graph of merge-sort to sort an array of size 7. The graph has roughly 2*log(n) layers, and each layer has n values. [1]
Code (almost python)
define mergesort(x):""" Sort array using merge sort algorithm """# base caseif length(x) <= 1: return x# split from middle. mergesort each half. then mergemiddle = length(x)/2a = 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