Merge Sort

This chapter covers merge sort, the first sort we write that runs in $O(n\log n)$. We write the merge of two sorted arrays, and then merge sort twice: bottom-up with loops, and top-down with recursion.

After reading this chapter, you should be able to:

• Trace and implement the two-pointer merge of two sorted arrays
• Analyze the merge: $O(n+m)$ time and auxiliary space on every input
• Explain why the in-place merge uses $O(1)$ auxiliary space but takes $O(n^2)$ time in the worst case
• Implement bottom-up merge sort with loops, for an array of any length
• Trace recursive merge sort: the splits on the way down, and the merges on the way up in depth-first order
• Implement merge sort recursively
• Analyze both versions of merge sort: $O(n\log n)$ time on every input and $O(n)$ auxiliary space
• Classify merge sort next to the quadratic sorts by time complexity class, auxiliary space, sensitivity to input order, and stability

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Merge Two Sorted Hands
2. Merge Two Sorted Arrays
3. Implementing the Merge Process
4. Complexity of the Merge Process
5. In-Place Merge
6. In-Place Merge: Analysis
7. The Common Way to Merge
8. Repeating the Merge Process
9. Bottom-Up Merge Sort
10. Merge Sort: Time and Space Complexity
11. Merge Sort: Best and Worst Case
12. Merge Sort for Any Length
13. Counting Up and Counting Down
14. A Top-Down Trace
15. Merge Sort, Recursively
16. Analyzing the Recursive Version
17. Properties of Merge Sort