Part of course:
Merge-sort: Video tutorial, pseudo-code and run-time analysis
- Merge-sort Algorithm
- GIF animation of Merge-sort
- Algorithm Steps
- Run-time analysis
- Code (almost python)
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.
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.
define mergesort(x):recursively sort first-half of xrecursively sort second-half of xmerge sorted halfs into single sorted array
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).
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 <= b):c.append(a)a.pop()else:c.append(b)b.pop()return c