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. Recursive functions are a powerful tool, but they can be a bit tricky to understand. They often work by breaking a problem down into smaller sub-problems of the same type.
In this case, we keep breaking the list into smaller parts and sorting those parts. 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 that means we can stop splitting.
Then it is time to merge the sorted lists back together. We merge 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.
