1
Classify a sort on four promises
Stability, in-place, adaptivity and comparison versus key-based — and pick one for a stated key domain and memory limit, which is a different question from picking the fastest.
Course · Algorithms
Sorting and Selection
Discrete Mathematics proved no comparison sort beats n log n. That leaves open everything that matters: stability, whether the bound applies at all, what randomness buys, and how close to the bound a real sort gets. This is also the course where the analysis becomes probabilistic — randomised quicksort's exact expectation is the pattern every later expectation on this path follows.
stable: equal keys keep input order ⟹ multi-key sort by successive passes
E[comparisons] = 2(n+1)Hₙ − 4n exact, and on EVERY input
counting sort: Θ(n + k) and k can be 2³²
T(n) ≤ T(n/5) + T(7n/10) + cn linear because 1/5 + 7/10 < 1
What this course is about
- Subject
- Algorithms
- Lessons
- 12
- Format
- Interactive
Overview
What you will be able to do
By the end you can classify any sort on four promises, derive randomised quicksort's expectation with indicator variables and check it against a measured mean, and prove a lower bound by playing an adversary.
2
Run seven algorithms by hand
Partition, quicksort, heapsort, counting sort, radix sort, quickselect and median of medians, each with its counter and its invariant.
3
Derive an expectation and check it
The indicator argument for 2(n+1)Hₙ − 4n, evaluated exactly as a fraction and compared with a mean over seeds — and the reason it holds for every input rather than for a typical one.
4
Prove a lower bound by adversary
Answer comparisons so as to keep the most outcomes alive, for the maximum, for min-and-max together, and for the second largest — then meet each bound with an algorithm.
Lessons
12 lessons
What a sort promises, then quicksort and the expectation it needs, then the sorts that escape the comparison bound by not comparing, then selection, then the lower bounds, then sorting at a scale where the cost model changes.
What a Sort Must PromiseClassify four sorts on four promises, then sort records on two keys by stable passes in the right order.Not marked
PartitioningPartition an array around a pivot in one pass, stating the three-region invariant at every step.Not marked
Quicksort and Its Worst CaseCount quicksort's comparisons on the input built to defeat the pivot rule you chose, and place the count in the recurrence.Not marked
Randomised QuicksortDerive the exact expected comparison count with indicator variables, and say why it holds for every input.Not marked
HeapsortRun heapsort by hand on eight keys, counting sift-down comparisons, and name the two promises it breaks.Not marked
Counting SortSort integer keys with a tally and a prefix sum, and say when the range makes it worse than a comparison sort.Not marked
Radix SortRun LSD radix sort on three-digit keys, and break it two ways to see what its correctness rests on.Not marked
Bucket Sort and Average-Case ClaimsState bucket sort's distributional assumption, compute the expected work, and build the input that makes it quadratic.Not marked
QuickselectFind the k-th smallest element without sorting, and give the argument for why a random pivot makes it expected linear.Not marked
Median of MediansChoose a pivot with a guarantee, solve the two-term recurrence by its level sums, and explain the group size.Not marked
Adversary ArgumentsProve three lower bounds by answering comparisons to keep the most outcomes alive, then meet each one with an algorithm.Not marked
k-Way Merging and Sorting in PracticeMerge k runs through a heap, count the passes a disk sort needs, and choose an insertion-sort cutoff from a measured crossover.Not marked
Recommended background
Searching and sorting, analysing iterative algorithms, divide and conquer, recursion trees and amortised analysis, expected value, linearity of expectation and permutations, all from discrete mathematics; and priority queues and binary heaps, and building a heap in linear time, from the data structures course on this path.
Practice suggestions
Read the pivot rule as a claim about inputs. Every deterministic rule has a bad input and the lab will build it; randomisation moves the randomness from the data to the algorithm, which is the whole distinction of “Randomised Quicksort”.
Count before you classify. A sort that is Θ(n + k) is linear only for the k you actually have, and the lab plots both terms.
Play the adversary. “Adversary Arguments” is the one place on this path where the reader is asked to defeat an algorithm rather than run one.
What it does not cover
Sorting networks and parallel sorts. The cost model here is sequential.
Shellsort, and Timsort's run-merging policy. Timsort's shape — runs, then merges, with insertion sort below a cutoff — is in “k-Way Merging and Sorting in Practice”; its galloping and run-stack rules are not.
Cache-oblivious analysis, and sorting linked lists.