Sorting and searching algorithms

The formula

C(n) ≥ log₂(n!) ≈ n·log₂ n − 1.44·n

The floor. Any sort that works by comparing pairs of items needs at least log₂(n!) comparisons in the worst case, because each comparison yields one bit and there are n! possible orderings to tell apart. For a million items that's about 18.5 million comparisons minimum — no comparison sort beats n·log₂ n by more than a constant.

T(n) = 2·T(n/2) + n   →   T(n) ≈ n·log₂ n

The mergesort recurrence: split in half, sort each half, merge in one linear pass. Halving depth is log₂ n, each level costs n, so the total is n·log₂ n — guaranteed, every input, every time.

Quicksort:  average ≈ 2·n·ln n ≈ 1.39·n·log₂ n    worst case  n²

Faster than mergesort on average and in place, but the guarantee is gone. Feed a naive-pivot quicksort already-sorted data and it degrades to n².

Binary search:  ⌈log₂(n+1)⌉ probes worst case

Each probe of a sorted table halves what's left. A million entries: 20 probes. A billion: 30. That's the whole pitch.

Heap layout (0-based array):  children of i are 2i+1, 2i+2;  parent is ⌊(i−1)/2⌋

A binary heap is a tree flattened into a plain array by arithmetic — no pointers. Heapsort rides it to a guaranteed n·log₂ n with zero extra memory.

Where you meet it

The post-test data crunch. A vibration run dumps ten million samples across forty channels and the report script has to merge time-stamped streams from three DAQ chassis into one timeline. That merge step — two sorted streams zipped into one in a single pass — is the inner organ of mergesort, and it's why the merge runs in seconds while a hand-rolled nested loop over the same data would still be going tomorrow. At n = 10⁶, n² is a factor of fifty thousand more work than n·log₂ n.
Lookup tables in embedded and flight code. Thermocouple linearization, cal curves, gain tables — all sorted arrays searched by binary search between samples. The successive-approximation ADC on your bench is the same algorithm cast in silicon: one halving decision per clock, one bit per step.
The review board question. Someone asks why the data-reduction pass takes forty minutes. The honest answer is usually an n² loop hiding in a script — a linear search inside a loop over rows. Sorting once and searching with log₂ n probes, or using a hash table, turns forty minutes into forty seconds. Knowing which of your loops is secretly quadratic is the whole literacy this entry exists to give you.
Real-time and safety-side code. When the worst case is what's certified, average-case speed is worthless. That's why the Linux kernel sorts with heapsort, and why C++ std::sort (introsort) runs quicksort but watches its own recursion depth and bails out to heapsort if an adversarial input starts dragging it toward n².

How it works

Sorting by comparisons is an information problem. There are n! ways the input could be ordered, a comparison answers one yes/no question, so you need log₂(n!) answers to pin down the ordering. Mergesort and heapsort meet that bound with a guarantee; quicksort meets it on average and gambles on the pivot. The gamble usually pays — quicksort's constant factors and cache behavior are better — which is why libraries build hybrids: quicksort until it misbehaves, heapsort as the safety net, insertion sort for the little subarrays where n² with a tiny constant beats n·log₂ n with a big one.

The property engineers overlook until it bites is stability: whether items that compare equal keep their original order. Mergesort is stable; quicksort and heapsort are not. Sort a telemetry table by timestamp, then stably sort by channel, and each channel's records are still in time order. Do the second sort with an unstable algorithm and the time order inside each channel is scrambled — a bug that only shows up as a plot that looks subtly wrong.

Binary search has one precondition and no mercy about it: the array must already be sorted by the exact comparison you're searching with. Hand it an unsorted array and it returns confident garbage — no error, no warning. Floating-point data adds a trap of its own: IEEE NaN compares false against everything, so a cal table with one NaN in it can "sort" into an inconsistent order and quietly break every search afterward. Scrub NaNs before you sort.

And binary search is famously hard to write correctly, in a way that should humble anyone. The classic midpoint line mid = (low + high)/2 overflows signed 32-bit arithmetic once the array passes 2³⁰ elements, sending mid negative. That exact bug sat in Java's official library binary search for about nine years before Joshua Bloch reported it in 2006 ^[8]. The fix costs nothing:

mid = low + (high − low)/2

Off-by-one errors in the loop bounds (< vs ≤, mid vs mid+1) are the other standard failure. Use the library routine. If you must write your own, test it at n = 0, 1, 2, at both ends, and with the target absent.

Two limits of validity worth knowing. First, the n·log₂ n floor only binds comparison sorts — if your keys are small integers, counting sort and radix sort run in linear time, which is how a flight-data tool can bin a billion 16-bit samples faster than any comparison sort could touch them. Second, big-O hides constants and memory traffic: on modern hardware a cache-friendly n·log₂ n sort can lose to a cache-hostile one by 3× at the same complexity, and for fewer than a few dozen items the dumb insertion sort wins outright.

History

Sorting is the oldest job in electronic computing. The first program John von Neumann worked out for the EDVAC, in 1945 — before the machine existed to run it — was a mergesort, drafted across 23 handwritten pages that Donald Knuth dug up and analyzed in 1970 ^[3]^[4]. A year later, in the 1946 Moore School Lectures that seeded the whole field, John Mauchly gave the first public description of binary search ^[5]^[6]. The idea took twenty minutes to explain; getting it right took longer. Published versions worked only for arrays of convenient sizes for years, with a cleanly general ALGOL implementation arriving via Hermann Bottenbruch in 1962 ^[5]^[6].

Quicksort came out of a language project, not a math department. In 1959–60, Tony Hoare was a visiting student at Moscow State University working on machine translation for the National Physical Laboratory, and needed to alphabetize the words of Russian sentences before looking them up in a dictionary stored on magnetic tape. The first idea he considered was too slow; the second was quicksort. He published it as ACM Algorithms 63 and 64 in 1961 and gave the full analysis in The Computer Journal in 1962 ^[1]^[2]. Heapsort arrived in 1964, when J.W.J. Williams published Algorithm 232 and, in the process, invented the binary heap as a data structure in its own right; Robert Floyd tightened it to fully in-place the same year ^[7]^[11].

The story didn't end in the sixties, which is the real lesson. In 2002 Tim Peters built Timsort for Python — a mergesort that exploits runs of already-ordered data — and it spread to Java and Android ^[9]. In 2015, researchers formally verifying it with the KeY prover found the same invariant flaw in the shipping Python, Java, and Android implementations — an invariant checked on three stacked runs when it needed to hold for all of them. In Java and Android the flaw could crash the sort on arrays as small as 2²⁶ elements (about 67 million); Python's more generous run-stack sizing pushed the breaking input beyond any practical memory, but all three were patched ^[9]^[10]. Between that and Bloch's overflow find ^[8], the record is clear: fifty-year-old algorithms, in the most heavily used libraries on Earth, still carried bugs. Respect the library, and test at the boundaries anyway.

Related tools

/tools/adc-resolution — a SAR converter is binary search implemented in hardware, one halving per clock, one bit per probe
/tools/resistor-e-series — nearest-value lookup in a sorted E-series table is exactly the search problem this entry describes
/tools/crest-factor — peak-finding over a capture is the degenerate search: one linear pass, no ordering to exploit

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →