02 — Sorting, heaps and binary search

Google asks one sorting question in writing: when is merge sort useful where quicksort is impractical? Have three reasons ready. The rest of this topic is binary search, and specifically the version that arrives disguised.

Prereqs: 01 · Reading: 6 min · Cards: 12 · Reference: sorting table

The map

Three tools that look separate and are not. Sorting is what you reach for when order unlocks a cheaper algorithm — two pointers, greedy selection, interval sweeps all begin with a sort. Heaps are what you reach for when you need the extreme but not the order, which is a surprisingly large fraction of problems. And binary search is what you reach for when a predicate is monotonic, which is more often than "the array is sorted" suggests.

The thread connecting them: each one trades completeness for cheapness. Sorting gives you total order at n log n. A heap gives you only the extreme, but at log n per operation. Binary search gives you one position, at log n total. Choosing correctly means knowing how little you can get away with.

What decides your score here

The merge sort question, answered with reasons rather than a definition. It is in the prep email verbatim, so it is not hypothetical. Three reasons is enough; five is showing off.

Recognising binary search on the answer. Everyone can binary search a sorted array. The version that separates candidates is realising that "the smallest k such that something is possible" is a binary search over the answer space, with a linear check per candidate. The array is not what you are searching.

Not reaching for a heavier tool than the problem needs. Using Dijkstra where BFS works, or sorting when a heap of size k would do, reads as pattern-matching rather than judgement.

Why merge sort where quicksort is impractical

Merge sort is O(n log n) in the worst case; quicksort degrades to quadratic. Wherever tail latency matters, or wherever an adversary picks the input, that guarantee is worth more than quicksort's better constant factor.

Merge sort is stable. If you sort by one field and then another, only a stable sort preserves the first as a tiebreak. Quicksort scrambles it.

Merge sort reads sequentially, which is what makes external sorting possible: you merge runs streamed from disk or network without ever holding the whole dataset. Quicksort needs random access to partition, so it simply cannot do this.

Two more, if you want them: merge sort on a linked list merges by relinking pointers, which is O(1) extra space and needs no indexing, whereas quicksort on a list is poor because partitioning requires random access. And the two halves are independent with a predictable merge, which is why it parallelises — it is essentially what MapReduce does.

And if they ask what Python actually uses: Timsort, a merge sort combined with insertion sort that detects already-ordered runs and merges them. Stable, linear on nearly-sorted input, n log n worst case. Almost nobody can answer that, and it costs you nothing to know.

The two details that make a quicksort good

A random pivot. With a fixed pivot at the last element, already-sorted input — which is the most common real input there is — degrades to quadratic. One line of code prevents it.

Recursing into the smaller partition and looping on the larger one. Without it, the worst case uses O(n) of stack and can overflow. With it, the stack is bounded at log n. Both details are in code/sorts.py, commented.

The same partition logic gives you quickselect: the k-th smallest element in linear average time, by descending into only the side that contains the answer. The work is n + n/2 + n/4, which sums to 2n. When an interviewer expects an O(n log k) heap for "k-th largest", offering quickselect is the answer that lands.

Heaps, and the counterintuitive part

Python's heapq is a min-heap; negate the values for a max-heap. Push and pop are logarithmic, peeking is constant, and heapify is linear rather than n log n — because sifting a node down costs its height, most nodes are near the bottom, and half of them are leaves that cost nothing at all. The sum converges to 2n.

For the k largest elements you want a min-heap of size k. That inversion catches people. The reason is that the thing you need to check cheaply is the weakest candidate you are currently holding, so you know who to evict — and that is exactly what a min-heap's root gives you. It costs O(n log k) time and O(k) space, and it works on a stream that does not fit in memory, which is the real reason it exists.

Two heaps facing each other — a max-heap over the lower half, a min-heap over the upper — give you the median of a stream. Implementations in code/heap.py.

Binary search, and the version that hides

Use one template every time. Every off-by-one in binary search comes from improvising the bounds.

lo, hi = 0, len(a)              # [lo, hi) — hi is EXCLUSIVE
while lo < hi:
    mid = (lo + hi) // 2
    if condition(mid): hi = mid       # mid could still be the answer
    else:              lo = mid + 1   # mid is ruled out
return lo                             # first index where the condition holds

The invariant is that if the answer exists it lies inside the window, and the window strictly shrinks, which is also the termination argument.

What the template actually requires is not a sorted array — it is a monotonic predicate: false, false, then true, true. A sorted array is just the most common way to get one. Once you see that, binary search on the answer stops being a trick and becomes obvious: when the prompt asks for "the smallest speed that finishes in h hours", you search over speeds, not over the array, and checking one candidate is a linear pass. The trigger phrases are "the smallest k such that" and "minimise the maximum".

The stdlib has bisect_left and bisect_right. Knowing they exist and reaching for them scores on the coding axis.

Say it

Cover the answers. Out loud, in English.

Now do this

Four problems, in order. Write the template from memory each time rather than copying it.

1. Binary Search — 10 min. From memory, no reference.
2. Koko Eating Bananas — 25 min. Say out loud what you are searching over before writing.
3. Kth Largest Element in an Array — 25 min. Heap first, then quickselect.
4. Sort an Array — 30 min. Merge sort from scratch, narrating the invariant.

Stop when you can write the binary search template from memory with no off-by-one, and give the merge sort answer in under thirty seconds.