Sorting and Searching

SearchSearch and sort are the two problems almost every other algorithm eventually leans on — a system that can't find or order its own data quickly enough usually can't do much else quickly either. Knuth's exhaustive historical and mathematical treatment of both remains the field's standard reference¹.

Linear Search versus Binary Search

LinearLinear search checks every element in turn until it finds a match or runs out of elements — it makes no assumption about the data's order, and needs none, but in the worst case examines every single element: O(n).

Binary search is far faster, O(log n), but only works under one condition: the data must already be sorted. It repeatedly checks the middle element of the remaining range — if the target is smaller, discard the upper half; if larger, discard the lower half; if equal, done — halving the search space on every comparison. That halving is only valid because of the sortedness invariant: if the middle element is bigger than the target, every element after it is guaranteed bigger too (because the array is sorted), so the entire upper half can be discarded with certainty, not just a guess. Break the sortedness and that guarantee — and the whole algorithm — breaks with it.

Bubble Sort versus Merge Sort

BubbleBubble sort repeatedly steps through the list, swapping adjacent elements that are in the wrong order, until a full pass makes no swaps. It's rarely used in practice — O(n²) in the average and worst case — but it earns its place in teaching because it's the simplest sort to trace by hand and reason about correctness for: after each full pass, at least one more element is guaranteed to have "bubbled" into its final correct position.

Merge sort takes the opposite strategy: split the list in half, recursively sort each half, then merge the two sorted halves back together in one linear pass. Splitting always down to single elements (trivially sorted) and merging back up gives O(n log n) — the log n comes from how many times the list can be halved, and the n comes from the linear-time merge needed at each of those log n levels.

merge_sort([8, 3, 5, 1])
  split -> [8, 3] and [5, 1]
    split -> [8] and [3]        (already sorted, length 1)
    merge -> [3, 8]
    split -> [5] and [1]
    merge -> [1, 5]
  merge [3, 8] and [1, 5] -> [1, 3, 5, 8]

That O(n log n) bound isn't a property of merge sort specifically — it's the best any comparison-based sort (one that can only ever ask "is A before B?") can achieve, provable with a decision-tree argument: any comparison sort's execution can be modelled as a binary tree of possible comparison outcomes, that tree needs at least n! leaves (one per possible input ordering), and a binary tree with n! leaves needs at least log₂(n!) levels — which is Θ(n log n) by Stirling's approximation². This is why merge sort, heapsort, and other O(n log n) sorts are considered asymptotically optimal for the general comparison-sorting problem, even though bubble sort remains easier to explain to someone seeing sorting for the first time.

Insertion Sort versus Quicksort

InsertionInsertion sort builds up a sorted prefix one element at a time: take the next unsorted element and shift it leftward past every already-sorted element bigger than it, until it lands in its correct place among them.

insertion_sort([8, 3, 5, 1])
  [8 | 3, 5, 1]   take 3, shift 8 right       -> [3, 8 | 5, 1]
  [3, 8 | 5, 1]   take 5, shift 8 right        -> [3, 5, 8 | 1]
  [3, 5, 8 | 1]   take 1, shift 8, 5, 3 right   -> [1, 3, 5, 8]

Like bubble sort, insertion sort is O(n²) in the average and worst case — but unlike bubble sort, it's genuinely used in production code, because it's adaptive: on data that's already sorted or nearly so, every shift step terminates almost immediately, and the whole sort collapses to O(n). That's exactly why real-world hybrid sorts (Python and Java's Timsort, many C++ standard library implementations' introsort) fall back to insertion sort once a recursive sort's partitions get small — below a few dozen elements, insertion sort's low constant-factor overhead beats an O(n log n) algorithm's actual wall-clock time, even though its asymptotic complexity is worse.

Quicksort takes a different strategy from merge sort's split-in-the-middle: pick a pivot element, partition the rest of the list into everything smaller than the pivot and everything larger, then recursively sort each partition — the pivot itself is already in its final position once partitioning finishes, needing no further work³.

quicksort([8, 3, 5, 1])
  pivot = 8 (last element)
  partition -> [3, 5, 1] all smaller, [] larger, 8 fixed in place
  quicksort([3, 5, 1])
    pivot = 1, partition -> [] smaller, [3, 5] larger, 1 fixed in place
    quicksort([3, 5]) -> pivot 3, partition -> [], [5] -> already sorted: [3, 5]
  result: [1, 3, 5, 8]

Quicksort's average case is O(n log n) — each partition step is O(n), and a pivot that lands anywhere near the middle halves the remaining work, giving the same log n depth as merge sort. But that bound depends entirely on the pivot actually splitting the data roughly evenly, and nothing about the algorithm guarantees that: pick the last element as the pivot (a common naive choice) and run it on data that's already sorted, and every partition splits into "nothing smaller, everything else" — the recursion depth becomes n instead of log n, and the whole sort degrades to O(n²), the exact same complexity class as bubble sort, on exactly the input that looks like it should be the easy case. This is precisely the kind of hidden scaling problem the next section's empirical doubling test is built to catch: a naive quicksort that looks fast on random test data can still hide an O(n²) worst case that a hand-built fixture would never happen to trigger. The practical fix is to make the bad case implausible rather than trying to rule it out entirely — choosing the pivot at random, or as the median of the first, middle, and last elements, makes the already-sorted-input pathology vanishingly unlikely without changing the algorithm's basic structure at all.

Measuring Performance Empirically

Big-OBig-O notation describes how an algorithm's cost scales, not how fast it runs on any one input — and trusting a complexity class without checking it empirically is a real way to be wrong about a program's actual behaviour. The practical method: time the same algorithm on inputs of several increasing sizes — doubling the input size each time is a good default — and look at how the runtime scales, not just whether it "seems fast enough" on whatever test data happens to be at hand.

Input doubles	O(n) runtime	O(n log n) runtime	O(n²) runtime
Expected ratio	~2×	~2× (plus a little)	~4×

A doubling that takes roughly 4× as long each time it doubles is the empirical signature of hidden O(n²) behaviour — worth checking directly on at least three or four increasing sizes before trusting any algorithm's assumed complexity, rather than reasoning about it from the code alone and never actually measuring it. A hand-built test fixture with a handful of items is usually far too small to expose this kind of scaling problem; it takes genuinely larger inputs to see the curve bend.

Pseudocode versus Program Source

PseudocodePseudocode deliberately strips away a specific language's syntax to leave only the algorithm's logical structure — useful for comparing two algorithms' underlying strategy without getting distracted by, say, Python's indentation rules versus Java's braces. But pseudocode is not a specification precise enough to run, and the translation from pseudocode to working source code is where off-by-one errors, incorrect loop bounds, and edge cases (an empty list, a single-element list) most often creep in — the algorithm can be correct in pseudocode and still wrong in the implementation, which is exactly why testing an implementation against its pseudocode's intent matters, not just reading the pseudocode and assuming the code that followed it is faithful.

References