Module 14
Sorting and Divide & Conquer
How the important sorts work inside, why O(n log n) is the limit for comparison sorts, and how to use sorting and partitioning as tools.
You'll rarely write a sort at work, but interviews test sorting for three reasons: merge sort and quick sort are the clearest examples of divide and conquer, their partition and merge steps solve other problems (Kth largest, counting inversions), and choosing the right sort order turns many hard problems into a simple scan.
The module covers stability and the n log n lower bound, merge sort, quick sort and quickselect, the non-comparison sorts (counting, radix, bucket), and custom comparators.
Best after: Recursion
Part 1
Learn the ideas
- 14.1Sorting Basics: Stability and the n log n LimitSimple sorts are O(n²); good comparison sorts are O(n log n), which is provably the best possible; stability decides whether equal items keep their order.14 min
- 14.2Merge SortSplit in half, sort each half recursively, merge the two sorted halves with two pointers. Always O(n log n), stable, O(n) extra space.15 min
- 14.3Quick Sort and QuickselectPartition around a pivot so smaller values go left and larger go right, then recurse on both sides (sort) or only one side (select the kth).16 min
- 14.4Counting, Radix and Bucket SortWhen keys are small integers or fixed-width, count them or distribute them instead of comparing: O(n + k) time.12 min
- 14.5Sorting as a ToolSort first, then scan: neighbours become comparable, duplicates sit together, and greedy choices become obvious.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Write merge sort and quick sort yourself, and know their trade-offs.
Three-way partitioning (Dutch national flag) in one pass with three pointers.
Quickselect: partition once and recurse into only the side that holds the answer, O(n) on average.
A custom comparator: put a before b when a + b (as strings) is bigger than b + a.
Counting sort with a custom order: count values, emit them in the given order, then the rest ascending.
Piggyback on merge sort: when an element from the right half is merged first, it forms an inversion with every element left in the left half.