Sorting in Linear Time

By the end of this lesson you will be able to prove WHY no comparison-based sort (insertion sort, merge sort, heapsort, quicksort) can ever beat Ω(n lg n) in the worst case, and then trace three algorithms that legally beat that bound anyway — countingSort, radixSort, and bucketSort — by looking at the actual VALUES being sorted instead of only comparing pairs of elements. All arrays are 0-indexed, exactly like the Dart code.

1. Why comparison sorts have a floor: the Ω(n lg n) lower bound

Merge sort and heapsort guarantee O(n lg n) in the worst case; quicksort guarantees it only on average. All four sorts you've met so far (insertion, merge, heap, quick) are comparison sorts: the only thing they ever learn about two elements is the answer to "is a[i] ≤ a[j]?" — never the actual numeric value. So here is the question: is O(n lg n) actually the best ANY comparison sort could ever do, or are we just not clever enough yet?

The answer comes from the decision-tree model: imagine drawing every possible sequence of comparisons a sorting algorithm could make on n elements as one giant binary tree. Every internal node is one comparison "a_i : a_j?"; the left branch is taken if the answer is "≤", the right branch if ">". Follow one root-to-leaf path and you've traced exactly one full execution of the algorithm on one specific input ordering. Because a CORRECT sorting algorithm must end up at a DIFFERENT leaf for every one of the n! possible input orderings (otherwise it couldn't tell two different orderings apart), every decision tree for a correct comparison sort must have at least n! reachable leaves.

Insertion sort is a comparison sort, so it has its own decision tree. Here is that exact tree for n = 3 elements — watch it get built, one input ordering at a time, by literally running insertion sort on every one of the 3! = 6 possible orderings of (a₀, a₁, a₂):

In Dart: insertion sort run on every ordering of n distinct values; each comparison outcome string is one root-to-leaf path, so the number of distinct paths is the number of leaves (n! for every n) and the longest path is the tree height (n = 3: 6 leaves, height 3).

A binary tree of height h has at most 2^h leaves. So if the tree needs at least n! leaves, we need 2^h ≥ n!, i.e. h ≥ lg(n!). Using Stirling's approximation (lg(n!) = Θ(n lg n)), this gives:

In Dart: merge sort’s worst-case comparison count W(n) = W(⌈n/2⌉) + W(⌊n/2⌋) + n − 1: it stays above ⌈lg n!⌉ for every n ≤ 200 and for n = 2²⁰ it is within 3% of lg(n!), which is what “asymptotically optimal” means.

Watch how fast n! — and therefore the minimum possible tree height ⌈lg(n!)⌉ — outgrows anything close to linear, even for tiny n:

In Dart: ⌈lg(n!)⌉ as a sum of logarithms (it reproduces the table above: 0, 1, 3, 5, 7, 10, 13, 16, 19, 22), together with the bounds n lg n − n lg e ≤ lg(n!) ≤ n lg n.

2. Counting sort

Counting sort assumes every input element is an integer in a known range 0 to k. It is not a comparison sort — it never asks "is this bigger than that?"; it only ever asks "how many elements equal exactly this value?", then converts those counts directly into final array positions. Here is the idea as pseudocode (a is the input, b the sorted output, counts the tally array, k the largest possible value):

Now trace it on a small example, one step at a time — watch a (input), counts (the tally array, indexed by VALUE) and b (the output being filled in) all at once:

Now an array with many repeated values — the case where STABILITY (preserving the original relative order of equal elements) actually matters and is visible. The little subscript next to each number is its original 0-indexed position in a, so you can watch exactly where each copy of a repeated value ends up in b:

Try your own array (non-negative whole numbers, comma-separated):

Why stability matters here at all: counting sort on its own doesn't care about stability — the numbers alone can't tell you if it stayed stable or not. Stability matters because counting sort is about to become the inner subroutine of radix sort in the next section, and radix sort's correctness proof depends entirely on every one of its digit-by-digit passes being stable.

Running time. Count the cost of every row of the pseudocode:

In Dart: counting every step of the four phases (counts zeroed: k + 1, tally: n, prefix sums: k, placement: n) gives exactly 2n + 2k + 1 = Θ(n + k): n = 10, k = 10 → 41 steps; n = 1000, k = 10 → 2021; n = 10, k = 10⁶ → 2 000 021, so a huge k dominates.

Correctness idea (loop invariant for the placement loop, rows 8–10): at the start of each iteration with index j, for every value v, counts[v] = (the number of elements of a smaller than v) + (the number of elements equal to v inside a[0..j]), i.e. counts[v] − 1 is the slot of the right-most copy of v that is not placed yet; and every slot of b already filled holds its final, correct, stably-ordered value. Before the first iteration: j = n − 1, so a[0..j] is the whole array and counts[v] straight out of the prefix-sum step is the number of elements ≤ v = (smaller than v) + (equal to v). Each iteration keeps it true: placing a[j] at b[counts[a[j]] − 1] is correct because that is exactly the right-most still-open slot for that value — and decrementing counts[a[j]] keeps the invariant true for j − 1. When the loop ends: at j = −1 every element has been placed, so b holds the fully sorted, stable output. ∎

In Dart: the invariant checked by brute force before every placement on the page example and on random arrays (slot c[v] − 1 is the 0-indexed output index).

The Dart translation below uses exactly the same indices as the pseudocode: a[0..n-1], and counts[0..k] is indexed by VALUE, not position, so it starts at 0 either way. The downward loop is a plain for (var j = n - 1; j >= 0; j--):

List<int> countingSort(List<int> a) {
  if (a.isEmpty) return [];
  final k = a.reduce(max);              // largest value in a
  final c = List<int>.filled(k + 1, 0);
  for (final v in a) {
    c[v] = c[v] + 1;                     // tally
  }
  for (var i = 1; i <= k; i++) {
    c[i] = c[i] + c[i - 1];              // prefix sums: count of elements <= i
  }
  final b = List<int>.filled(a.length, 0);
  for (var j = a.length - 1; j >= 0; j--) {   // downto -> STABLE
    b[c[a[j]] - 1] = a[j];
    c[a[j]] = c[a[j]] - 1;
  }
  return b;
}

In Dart: the (key, payload) version of counting sort that radix sort calls for each digit; MapEntry.key is the digit and .value is the whole number carried along.

3. Radix sort

Radix sort sorts multi-digit numbers by repeatedly counting-sorting on ONE digit position at a time — crucially, starting from the least-significant digit (LSD), not the most-significant one (which is the "obvious" but wrong-headed first instinct). Its pseudocode is almost embarrassingly short (digit position 0 is the ones place):

Cost of radix sort. Given n numbers of d digits each, where each digit takes up to k possible values, radix sort correctly sorts them in Θ(d(n + k)) time, provided the stable sort used for each digit takes Θ(n + k) — exactly what counting sort gives us. Trace it on a list of seven 3-digit numbers, one full digit-pass at a time:

Numbers with different numbers of digits are handled automatically: a "missing" high digit is simply digit value 0 (an implicit leading zero) once the digit-extraction place value exceeds the number:

Try your own list of non-negative whole numbers:

Correctness (by induction on the digit position). Base case: after sorting by digit 0 alone, the array is correctly sorted by digit 0. Inductive step: assume after passes 0..i-1 the array is correctly sorted by its low-order i digits (as a number). Pass i stably sorts by digit i. Two elements with different digit-i values end up correctly ordered by that pass. Two elements with the same digit-i value are left in whatever relative order they already had — and by the inductive hypothesis, that order is already correct on the lower i digits, which (since digit i is tied) is exactly the correct final order for their low-order i+1 digits too. This is precisely where the stability of each pass gets used. ∎

In Dart: the induction of the correctness proof, checked: after pass i the list is sorted by its low i digits (value mod 10ⁱ).

Choosing the digit size. For n numbers of b bits each, viewed as d = ⌈b/r⌉ digits of r bits (so k = 2^r - 1): total time is Θ((b/r)(n + 2^r)). If b < ⌊lg n⌋, pick r = b — a single pass, Θ(n). Otherwise pick r = ⌊lg n⌋, giving Θ(bn / lg n) — for b = O(lg n) (e.g. sorting n numbers in the range [0, n^c) for constant c), that's Θ(n), beating any comparison sort's Ω(n lg n) floor. The trade-off: radix sort (via counting sort) is not in-place, and its per-pass overhead often loses to a well-tuned quicksort in practice despite the better asymptotic bound, because quicksort has better cache locality.

In Dart: the digit-size rule in code: b-bit keys cut into r-bit digits need d = ⌈b/r⌉ passes of counting sort with k = 2^r − 1; radixCost is (b/r)(n + 2^r) and bestR finds the best r by brute force (n = 2¹⁶, b = 32: r = 11 costs 202 752, r = ⌊lg n⌋ = 16 costs 262 144; b = 8 < lg n: r = b, one pass).

Dart, using countingSortByKey to stably sort by one digit at a time (the digit becomes the "key", the whole original number is the "payload" carried through each pass):

List<int> radixSort(List<int> a) {
  if (a.isEmpty) return [];
  final maxV = a.reduce(max);
  var cur = List<int>.from(a);
  var place = 1;
  while (maxV ~/ place > 0) {                 // one pass per digit, LSD first
    final items = [for (final v in cur) MapEntry((v ~/ place) % 10, v)];
    final sorted = countingSortByKey(items, 9);  // stable! digits are 0..9
    cur = sorted.map((e) => e.value).toList();
    place *= 10;
  }
  return cur;
}

4. Bucket sort

Bucket sort assumes the input is n real numbers drawn roughly uniformly from [0, 1). It divides [0, 1) into n equal-width buckets, drops each element straight into its bucket by value, sorts each (usually tiny) bucket with insertion sort, then concatenates. Here it is on ten values spread fairly evenly across [0,1):

Now a smaller example that is easier to follow slowly — five values:

Worst case: if the values are NOT spread evenly — say they're all clustered near the same point — almost every element lands in the SAME bucket, and that one bucket's insertion sort degrades to Θ(n²):

In Dart: all n keys in one bucket: insertion sort shifts n(n−1)/2 times (n = 5: 10; n = 1000: 499 500), whereas uniform keys need only a few hundred shifts. The same panel checks the correctness step: ⌊n·a[i]⌋ never decreases along sorted input.

Try your own values in [0, 1):

Correctness. If a[i] ≤ a[j], then ⌊n·a[i]⌋ ≤ ⌊n·a[j]⌋ (the floor function is non-decreasing), so a[i]'s bucket index is never greater than a[j]'s. Elements in the SAME bucket are put in order by that bucket's own insertion sort. Elements in DIFFERENT buckets are already in the right relative order simply because the buckets are concatenated in increasing index order. Both cases covered ⇒ the final array is sorted. ∎

Average-case analysis. Let n_i be the (random) number of elements landing in bucket i. Total time is Θ(n) (the distribute + concatenate passes) plus Σᵢ O(n_i²) (the per-bucket insertion sorts). Using indicator random variables for "element j lands in bucket i", you get E[n_i²] = 2 - 1/n for every bucket, so:

In Dart: E[n_i²] = 2 − 1/n three ways: the indicator-variable formula n(1/n) + n(n−1)(1/n²), the exact Binomial(n, 1/n) sum, and a seeded simulation of the total work Σ n_i² (n = 1000: about 2n − 1 = 1999).

Summing that constant E[n_i²] bound over all n buckets gives E[T(n)] = Θ(n) + n · O(2 - 1/n) = Θ(n) — linear on average, exactly because a roughly-even spread keeps every bucket tiny.

Dart (buckets as List<List<double>>, clamped so floating-point edge values near 1.0 never index out of bounds):

List<double> bucketSort(List<double> a) {
  final n = a.length;
  if (n == 0) return [];
  final buckets = List.generate(n, (_) => <double>[]);
  for (final v in a) {
    var idx = (n * v).floor();
    if (idx < 0) idx = 0;
    if (idx > n - 1) idx = n - 1;
    buckets[idx].add(v);
  }
  for (final b in buckets) {
    insertionSortDoubles(b);
  }
  return buckets.expand((b) => b).toList();
}

In Dart: the per-bucket insertion sort used by bucketSort above.

5. Beyond the basics: the 0-1 sorting lemma & columnsort

Remarkably, yes. The 0-1 sorting lemma: if an oblivious compare-exchange algorithm correctly sorts every possible array made ONLY of 0s and 1s, then it correctly sorts EVERY array of arbitrary values. This shrinks the space of inputs you must check from n! arbitrary orderings down to just 2^n binary strings — a much smaller (and highly structured) set to verify.

In Dart: insertion sort written as a fixed list of compare-exchange pairs; the lemma says testing all 2ⁿ binary inputs is enough, and the code checks both that and all n! orderings for n = 1..8 (a network with one comparator removed fails both).

In Dart: the eight columnsort steps on a flat column-major list (r = 18, s = 3 satisfies s | r, r even, r ≥ 2(s−1)² = 8); steps 2 and 4 are index maps between column-major and row-major order.

This is a genuinely different FLAVOR of correctness argument than anything else in this lesson — instead of a loop invariant or an inductive argument over passes, it's a reduction: "if this special restricted family of inputs (0s and 1s) always works, then EVERYTHING works." The same "restrict to a smaller but sufficient test set" idea shows up again when proving sorting networks and parallel merging algorithms correct.

Quiz

Interview questions

Cheat sheet