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¹.

A sort is rarely chosen in the abstract. "The best sort" depends on what is known about the data (its size, whether it is already partly ordered, the range of its keys), on what the result must preserve (the order of equal keys, for instance), and on what the machine makes expensive (comparisons, moves, or disk reads). The sections below build up the algorithms that answer those different needs, and the decision table further down brings them together.

Linear Search versus Binary Search FoundationalKnowledge that endures for decades — core principles

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 FoundationalKnowledge that endures for decades — core principles

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.cf. divide and conquer, generalised

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. The bound applies only when order is discovered by comparing pairs of elements; the section on going beyond the comparison bound looks at what happens when it is not.n! leaves force the log n depth

Insertion Sort versus Quicksort FoundationalKnowledge that endures for decades — core principles

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). The cases where that matters are set out below.

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 empirical doubling test below 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.

Choosing a Sort Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

AA generic sort is the right answer only when nothing is known about the data or the result. The useful question is what is known that allows something better. The table below sets out the main algorithms by the property each one exploits. It is a decision table, not a league table: no row is the best sort, and each is the best choice for some combination of conditions.

Every row answers a different question. Read the last column first: it names the condition that makes an algorithm the right choice, and the other columns say what that choice costs.

When Insertion Sort Earns Its Place Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

SmallSmall collections. For small n, recursion, partitioning, allocation, and function-call overhead can outweigh asymptotic advantages. A simple quadratic algorithm may finish sooner than a more elaborate O(n log n) one.

Nearly sorted collections. Insertion sort's work depends on how far elements must move, not merely on the length of the collection. If only a few elements are out of position, it can approach linear time.

Incrementally maintained order. If records arrive one at a time and the existing sequence is already sorted, each new item can be inserted at its correct position. This makes insertion sort relevant to maintaining order, not only to batch sorting.

Small partitions in hybrid algorithms. Production routines rarely commit to one textbook algorithm. Introsort, described below, is typically implemented to finish small partitions with insertion sort.

Selection Sort, and Comparisons versus Writes Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

SelectionSelection sort repeatedly finds the smallest remaining item and places it into the next output position. It remains O(n²) even on sorted input, so it is not a serious general competitor to insertion sort. Its distinctive property is that it performs only O(n) swaps, which makes it useful for an engineering point rather than for speed:

Comparisons and writes do not always have the same cost. Selection sort may be worth considering when the collection is small, when writes to storage are expensive, when moving records costs far more than comparing their keys, or when the teaching goal is to distinguish the number of comparisons from the number of movements.

Compared directly with insertion sort: insertion sort often performs fewer comparisons on nearly sorted data; selection sort performs a predictable number of comparisons; selection sort may perform fewer writes; and both remain quadratic in the general case.

Heapsort and Introsort Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

HeapsortHeapsort completes the comparison-sort story between merge sort and quicksort. Williams introduced it in 1964, building the array into a binary heap and repeatedly removing the largest element⁴. It runs in O(n log n) in the worst case, operates in place without merge sort's linear auxiliary array, and avoids quicksort's quadratic worst case. It is not stable, and its memory access pattern is less favourable than quicksort's, so in practice it may be slower than a well-implemented quicksort.

Heapsort's most useful role is conceptual. Each algorithm so far makes a different trade-off between average time, worst-case time, auxiliary storage, stability, and locality. Heapsort gives up locality and stability to obtain a worst-case bound and in-place operation.

Introsort combines the two. Musser's 1997 algorithm begins as quicksort and monitors the depth of recursion. When the partitioning appears to be degenerating, it switches to heapsort, which keeps the worst case at O(n log n)⁵. Most inputs are handled by quicksort's fast path, and the heapsort fallback is rarely reached.

Beyond the Comparison Bound Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

TheThe Ω(n log n) bound from earlier applies only when order is discovered solely by comparing pairs of elements. When keys have structure that can be exploited, a different route opens.

Counting sort is useful when keys are integers, the key range is known, that range is not excessively large relative to the number of records, and memory for the counts is acceptable. Sorting a million examination marks in the range 0 to 100 needs no pairwise comparison at all: count how many times each mark occurs, then reconstruct the ordered sequence. The running time is O(n + k), where k is the size of the key range.

The same method fails on the other side of the trade-off. Sorting 100 records whose keys may range from 0 to 10¹² would require a count array far larger than the data it describes, so a comparison sort is the better choice there.

Radix sort sorts structured keys one component at a time: the digits of an integer, the bytes of an identifier, a fixed-width string, or a date broken into year, month, and day. The key idea is not that radix sort is universally faster. It is that knowledge about the representation of the keys can avoid the general comparison model. Each pass must be stable, so that the ordering established by earlier passes is preserved.

Stability as a Selection Criterion Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

AA stable sort preserves the existing order of records whose sort keys compare equal. Consider three records sorted by year:

Original order:          Stable sort by year:
(Musa, year 2)           (Chen, year 1)
(Chen, year 1)           (Musa, year 2)
(Patel, year 2)          (Patel, year 2)

Musa stays before Patel because their year keys are equal, and the original order of the two is kept. Stability matters when records carry several fields, when stable sorts are composed one after another, when the previous ordering carries meaning, and when users expect ties to keep the order they can already see. Radix sort depends on it for exactly this reason.

Standard libraries make these guarantees explicitly. Python's sorting documentation states that sorts "are guaranteed to be stable", and that the key function "is called exactly once for each input record"⁶. Java distinguishes two cases. Sorting an object array is guaranteed to be stable, and the implementation is a stable, adaptive, iterative mergesort. Sorting a primitive array, such as an int[], uses a dual-pivot quicksort, and its documentation makes no stability promise, which is harmless for plain numbers but matters for records⁷.

What Production Sorts Actually Do Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

ProductionProduction libraries generally use hybrid and adaptive strategies rather than one textbook algorithm. Python's list sort is Timsort, which takes advantage of any ordering already present in the data⁶. Java's object sort is a stable mergesort, while its primitive sort is a dual-pivot quicksort, so a single statement that "Java uses Timsort" is not accurate for both. Many C++ standard library implementations use introspective strategies that combine quicksort, heapsort, and insertion sort.

A production sort may therefore switch methods according to partition size, recursion depth, existing ordered runs, whether the data is primitive or object-valued, whether stability is required, and implementation-specific tuning. Reading a library's documentation is part of choosing it.

When the Data Does Not Fit in Memory Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

EverythingEverything so far has assumed that the data fits in RAM. External merge sort handles data that does not. It reads a chunk that fits in memory, sorts the chunk, writes the sorted run to external storage, and repeats for the rest of the data. Finally it performs a multi-way merge of the sorted runs, organised to reduce costly transfers between storage and memory.

This supports a general lesson. The relevant cost model is part of the algorithm. For an in-memory sort, comparisons and movements may dominate. For an external sort, block reads, writes, and merge passes matter far more than CPU operations, so the same O(n log n) label hides very different real costs.

Partial Sorting and the Top k Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

NotNot every task needs a complete ordering. Examples include the ten highest scores, the hundred most recent records, the five cheapest routes, the next scheduled event, or the median value. Sorting everything and taking the first k elements may do a great deal of unnecessary work. A bounded heap can keep the best k items in roughly O(n log k) time, which is attractive when k is much smaller than n.

The question to ask before sorting is whether the whole collection needs to be in order. It links directly to the material on trees and heaps.

An Algorithm-Selection Checklist Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

BeforeBefore choosing a sorting method, ask:

• How large is the input?
• Is it already partly ordered?
• Must equal keys keep their existing order?
• Does the data fit in memory?
• Are the keys drawn from a small or structured domain?
• Are comparisons expensive? Are writes or moves expensive?
• Is worst-case performance important?
• Is extra memory acceptable?
• Do we need a complete order, or only the smallest or largest few items?
• Is the input an array, a linked structure, a stream, or a file?
• Should a standard-library implementation be preferred to a handwritten sort?

Sorting algorithms are not interchangeable implementations of the same idea. Each exploits a different property of the data, the machine, or the required result. Choosing well means identifying which of those properties actually hold.

Measuring Performance Empirically Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

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.

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 Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

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.translation is where bugs creep in

Related Topics

• Divide and Conquer — merge sort's split/solve/combine strategy, covered here, generalised into the broader design technique and analysed with the Master Theorem.
• Trees, Heaps, and Graphs: Traversal and Construction — heapsort's structure, the bounded heap used for top-k selection, and why an in-order traversal of a binary search tree visits every node in sorted order for free.
• Data Structures as Behavioural Contracts — choosing a collection by its behavioural contract and algorithmic cost, the same discipline this page's empirical-doubling-test section applies to choosing between sorting algorithms.

References