Unit 2.1 · about 5 h
96 / 324Sorting contracts, lower bounds and merge sort
Sorting is the first place an ordering invariant pays off, and the lower bound tells you when to stop tuning comparisons and change the input assumptions instead.
- derive
- implement
You can now
- State the sorting contract (stability, in-place behavior, comparator rules) and pick merge sort, quicksort or heap sort from the binding constraint.
- Prove the comparison-sorting lower bound with a decision-tree argument and explain why counting and radix sorts escape it.
- Implement stable top-down merge sort with a shared auxiliary buffer and check it against
sortedwith randomized differential tests.
Covers
- Sorting stability, in-place behavior and comparator contracts
- Comparison lower bounds and non-comparison assumptions
- Stable merge sort and divide-combine reasoning
Study, in this order
5 steps
- Comparison sorts I: insertion sort and merge sortDSA Handbook - search, trees and heaps
Algorithm A: insertion sort; Algorithm B: merge sort; Why the merge step gives you \(\Theta(n \log n)\); The stability table; Worked example: merge sort on
[5, 2, 4, 7, 1, 3, 2, 6]; Pitfalls - Quicksort vs mergesort vs heapsort, picking your sortDSA Handbook Patterns - quicksort vs mergesort vs heapsort
The decision; Algorithms compared; Side-by-side; Common misconceptions
- Erickson Chapter 1: MergesortAlgorithms
Section 1.4 Mergesort (pp. 26 to 28), including Lemma 1.1 (Merge), Theorem 1.2 (MergeSort) and the recurrence analysis
- Lecture Note 12: Lower Bounds, decision trees and sortingAlgorithms
Sections 12.2 Decision Trees, 12.3 Information Theory, 12.4 But wait a second... and 12.5 Sorting
- Linear-time sorts: counting, radix, bucketDSA Handbook - search, trees and heaps
Three preconditions, three algorithms; Counting sort
Depth · Skim LSD radix sort and Bucket sort for their preconditions only (fixed-width keys; near-uniform keys). Only counting sort is implemented here.
Focus on
- Stability means equal keys keep their input order. Merge sort is stable because the merge emits the left run on ties (
<=, not<). Quicksort and heap sort are not stable. - The merge recurrence \(T(n) = 2T(n/2) + \Theta(n)\) gives \(\Theta(n \log n)\) in the best, average and worst case. The shared buffer costs \(\Theta(n)\) extra space plus \(\Theta(\log n)\) stack; the already-sorted short-circuit recovers \(\Theta(n)\) on sorted input.
- The lower bound counts leaves: \(n\) distinct keys admit \(n!\) permutations, so a decision tree needs height at least \(\lg(n!)\), which is \(\Omega(n \log n)\) by Stirling. It binds only comparison sorts on general input; counting sort never compares and needs bounded integer keys instead.
- Equal asymptotics do not mean equal speed in Python. On a 12th Gen Intel Core i9-12900K with Python 3.13.14, a pure-Python merge sort on 20,000 random ints took 0.018 s against 0.0017 s for
list.sort, about 10x. State the CPU and version with every timing you report.
Reproduce closed-book
lo + (hi - lo)//2, <= in the merge, and the already-sorted short-circuit. On [5, 2, 4, 7, 1, 3, 2, 6] it must return [1, 2, 2, 3, 4, 5, 6, 7]. Stability check: [(5, 'a'), (3, 'b'), (5, 'c')] must come back [(3, 'b'), (5, 'a'), (5, 'c')]. Then run a Hypothesis differential test against sorted on 300 lists up to length 60 with seed 0.Traps
- Using
<instead of<=in the merge. Ties taken from the right run break stability silently while every sortedness test still passes. - Allocating a fresh auxiliary list in every merge call. Allocate once at the top; per-call allocation adds a hidden linear factor at each of the \(\log n\) levels.
- Reading the lower bound as a ban on fast sorting. It bans fast comparison sorting on general input; bounded keys (counting) or fixed-width keys (radix) change the model and the bound does not apply.
Practice
Solve with your merge sort; example inputs [5,2,3,1] and [5,1,1,2,0,0]
Attempt before reading solutions. After submitting, read the AlgoMaster write-up for Sort an Array (https://algomaster.io/learn/dsa/sort-an-array) and compare its approach with yours.
LeetCode 88: Merge Sorted Array
Merge in place from the end with \(O(1)\) extra space; example inputs ([1,2,3,0,0,0], 3, [2,5,6], 3) and ([0], 0, [1], 1)
This is the merge step under a no-buffer constraint. After submitting, read the AlgoMaster write-up for Merge Sorted Array (https://algomaster.io/learn/dsa/merge-sorted-array).
Self-test
-
Prove that any comparison sort needs \(\Omega(n \log n)\) comparisons in the worst case.
Model the sort as a decision tree: each internal node is one comparison and each leaf is one output permutation. Sorting \(n\) distinct keys needs at least \(n!\) leaves. A binary tree with \(L\) leaves has height at least \(\lg L\), so the height is at least \(\lg(n!)\). By Stirling, \(n! > (n/e)^n\), so \(\lg(n!) > n \lg n - n \lg e = \Omega(n \log n)\). -
Why does counting sort not contradict that bound?
The bound counts comparisons on general input. Counting sort never compares keys; it indexes by key value, which needs bounded integer keys with \(k = O(n)\) for linear time. Change the assumption and the bound does not apply. -
Is Python's
list.sortstable, and how do you check from a REPL?Yes, it is Timsort and stable. Checksorted([(5, 'a'), (3, 'b'), (5, 'c')], key=lambda p: p[0]): the two 5s keep the order ('a') before ('c'). -
Why does merge sort cost \(\Theta(n \log n)\) even on already-sorted input without the short-circuit?
Every level still visits all \(n\) elements to merge, and there are about \(\log_2 n\) levels regardless of order. The short-circuit only skips the merge work when the two runs are already ordered, which recovers \(\Theta(n)\) on sorted input.
Completion criterion
Stop when
Your merge sort returns the sorted handbook example, keeps equal-key order, passes 300 Hypothesis cases against sorted, and you can state the decision-tree bound and the counting-sort precondition without notes.
Leads to
- 2.2 Partitioning, quicksort, quickselect and top-k Partition-based sorting and selection continue the comparison-sort story.
- 2.6 Heaps and priority queues Heap sort reuses the heap built there.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.