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.

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