Beating the n log n Barrier: Linear-Time Sorting Algorithms Explained

Why n log n Seems Like a Fundamental Barrier

Every comparison-based sorting algorithm discussed so far in this series — insertion sort, heapsort, and quicksort — achieves at best Θ(n log n) running time. This raises a natural question: is n log n a fundamental limit for sorting, or simply a limitation of the specific algorithms studied so far?

Proving the Ω(n log n) Lower Bound for Comparison Sorts

A Comparison Sort is any sorting algorithm that determines the relative order of elements only through comparisons between pairs of elements. This lower bound proof uses a Decision Tree model: an abstract binary tree representing every possible sequence of comparisons an algorithm might make, where each leaf corresponds to one possible final permutation of the input.

For n elements, there are n! possible permutations,
and each must correspond to at least one leaf in the decision tree

A binary tree with height h has at most 2^h leaves,
so the tree must satisfy: 2^h ≥ n!

Taking the logarithm of both sides:
h ≥ log₂(n!)

Using Stirling's approximation, log₂(n!) = Θ(n log n)

Therefore: h = Ω(n log n)

Since the height of the decision tree represents the worst-case number of comparisons the algorithm performs, this proves that any comparison-based sorting algorithm must make Ω(n log n) comparisons in the worst case. This means heapsort and merge sort, both achieving Θ(n log n), are Asymptotically Optimal among comparison-based algorithms — no comparison sort can do fundamentally better.

Breaking the Barrier: Sorting Without Comparisons

The Ω(n log n) lower bound applies specifically to comparison-based algorithms. If an algorithm can exploit additional information about the elements being sorted, such as knowing they are integers within a bounded range, it can sort in linear time by avoiding comparisons entirely.

Counting Sort: Exploiting a Known Small Range

Counting Sort works when the input consists of integers within a known range [0, k]. Rather than comparing elements, it counts how many elements equal each possible value, then uses these counts to determine each element's final position directly.

COUNTING-SORT(A, B, n, k):
  let C[0..k] be a new array, initialized to 0
  for i = 1 to n:
      C[A[i]] = C[A[i]] + 1
  // C[i] now contains the number of elements equal to i

  for i = 1 to k:
      C[i] = C[i] + C[i - 1]
  // C[i] now contains the number of elements ≤ i

  for i = n downto 1:
      B[C[A[i]]] = A[i]
      C[A[i]] = C[A[i]] - 1
  return B

Working through a small example with input [2, 5, 3, 0, 2, 3, 0, 3] and range [0, 5]:

Counting step, C[v] = count of value v:
C = [2, 0, 2, 3, 0, 1]   (indices 0 through 5)

Cumulative step, C[v] = count of values ≤ v:
C = [2, 2, 4, 7, 7, 8]

Placing elements from the end of A (for stability),
using cumulative counts to find each element's position,
produces the sorted output: [0, 0, 2, 2, 3, 3, 3, 5]

The algorithm runs in Θ(n + k) time — genuinely linear when k = O(n). An important property is Stability: elements with equal values retain their original relative order, which matters when counting sort is used as a subroutine, as it is in radix sort below.

Radix Sort: Extending Counting Sort to Multi-Digit Numbers

Radix Sort extends the range-limited approach of counting sort to numbers with many digits, by sorting one digit position at a time, from the least significant digit to the most significant.

RADIX-SORT(A, n, d):
  for i = 1 to d:
      use a stable sort to sort array A on digit i
      (typically counting sort, since digits have a small range)

The key insight that makes this correct is subtle: sorting must proceed from the least significant digit to the most significant, and the sort used at each digit position must be Stable, preserving relative order among elements with equal digits at that position. This ensures that once the most significant digit is sorted last, any ties are already correctly broken by the lower-order digits sorted in previous passes.

Example sorting 3-digit numbers:
[329, 457, 657, 839, 436, 720, 355]

After sorting by 1s digit (stable):
[720, 355, 436, 457, 657, 329, 839]

After sorting by 10s digit (stable):
[720, 329, 436, 839, 355, 457, 657]

After sorting by 100s digit (stable):
[329, 355, 436, 457, 657, 720, 839]  — fully sorted

If each of the d digit passes uses counting sort with digits in range [0, k], each pass costs Θ(n + k), giving a total running time of Θ(d(n + k)). For fixed-size integers, such as 32-bit or 64-bit numbers with a constant number of digits, this is Θ(n), genuinely linear time.

Bucket Sort: Exploiting a Known Uniform Distribution

Bucket Sort works well when input elements are assumed to be uniformly distributed over a known range, typically the real interval [0, 1). It divides this range into n equal-sized buckets, distributes elements into their corresponding bucket, sorts each bucket individually (typically with insertion sort, since buckets are expected to contain few elements), and concatenates the results.

BUCKET-SORT(A, n):
  let B[0..n-1] be new empty lists (buckets)
  for i = 1 to n:
      insert A[i] into list B[⌊n · A[i]⌋]
  for i = 0 to n - 1:
      sort list B[i] with insertion sort
  concatenate the lists B[0], B[1], ..., B[n-1] in order

Under the assumption of a uniform input distribution, the expected number of elements per bucket is O(1), so sorting each small bucket with insertion sort takes expected constant time, giving an overall expected running time of Θ(n). This is an average-case guarantee, connecting directly to the probabilistic analysis techniques discussed earlier in this series, rather than a worst-case guarantee — if the distribution assumption fails and all elements land in one bucket, performance degrades to that of insertion sort alone.

Choosing the Right Linear-Time Algorithm

Each of these three algorithms trades generality for speed by exploiting a specific assumption about the input.

Counting sort: requires integers in a small known range [0, k]
Radix sort:    requires fixed-digit numbers (or fixed-length keys)
Bucket sort:   requires input uniformly distributed over a known range

If none of these assumptions hold, comparison sorts
like heapsort, merge sort, or quicksort remain the
correct general-purpose choice, bounded by Ω(n log n)

Why This Trade-off Between Assumptions and Speed Matters

These linear-time algorithms illustrate a recurring theme in algorithm design: exploiting known structure or constraints on the input can allow an algorithm to circumvent a general-purpose lower bound that applies only to a broader, less-informed class of algorithms. Recognizing when input data satisfies the specific assumptions required by counting sort, radix sort, or bucket sort can turn an otherwise Θ(n log n) sorting task into a genuinely linear-time one, a significant practical improvement for very large datasets.