Part of course:
- GIF animation
- Code (almost python)
- Other notes
This video explains the merge-sort algorithm really well, and it does so in 3 minutes! The second half of the video is a race between merge-sort and quick-sort and I'm surprised how well it highlights the intricacies.
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). Its at-least as important to understand this intuitively as it is to understand it rigorously.
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
You can also read a text description of the algorithm on IARCS Online Study Material. For a bonus video, a classic exercise on merge-sort, and more information, check out the responses to this discussion.
Source (for GIF and graphic): Wikipedia