1 How to MergeSort a list
2 if list has length <= 1
3 A list of one thing or no things is already sorted!
4 Do nothing
5 else
6 listA = first half of list
7 listB = second half of list
8 We split the lists, now sort each half by doing MergeSort on them
9 Do MergeSort on listA
10 Do MergeSort on listB
11 Do Merge on listA, listB back into list
It looks almost like cheating… How do you sort a list? You cut it in half and sort each half, then merge the halves together! Note that the definition for MergeSort calls MergeSort on the halves of the list - that means it is a recursive definition, a function that is defined in terms of itself. So your initial list gets split into 2 halves. Each half gets split into 2 halves. Each of those gets split in half again… Until, finally, we have lists of size 1. A list of size 1 is always sorted, so then we start merging the sorted lists of length 1 back into a sorted list of length 2. Then we merge the sorted lists of length 2 back into a sorted list of length 4…
The video and animation below merge lists in a slightly different order than the pseudocode. According to the pseudocode (and real implementations of Merge Sort), we would merge indexes 1 and 2, then 3 and 4, then {1, 2} and {3, 4}, then 5 and 6, then 7 and 8, then {5, 6} and {7, 8}, then finally {1, 2, 3, 4} and {5, 6, 7, 8}. Basically, we always go do as much as we can on the left half of the list we are working on, then backtrack to the right side. This order does not change anything about the efficiency or general process, but if you run the pseudocode algorithm by hand you will notice differences from the video/animation.
