MergeSort
Input: a list of n numbers
Output: same n numbers in sorted order
Algorithm:
- Recursively sort 1st half
- Recursively sort 2nd half
- Merge 2 sorted lists together (tricky part)
When merging the 2 sorted lists the head of each list is the only candidate element for the head node of the final list.
Specific pseudo-code Running Time of MergeSort
Generalized Running Time of MergeSort
