Suggest an edit

Improve this article

Refine the answer for “What is the complexity of the fastest sorting algorithm? Why can't it be made faster?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

For any general-purpose comparison sort, the minimum achievable asymptotics is Θ(n log n) in the number of comparisons (on average and in the worst case). It cannot be made faster, because any comparison sort must distinguish n! permutations, and a binary decision tree requires at least log2(n!) ≈ n log2 n − 1.44n comparisons. Linear time O(n) is possible only under additional constraints on the keys (for example, integers from a bounded range - counting/radix sort).

## Detailed breakdown

### Bounds for comparison sorts

- Lower bound: any comparison sort requires Ω(n log n) comparisons.
- Upper bound: algorithms with O(n log n) complexity exist - merge sort, heap sort (worst case), quicksort (average case).
- Summary: the optimal asymptotics for comparison-based algorithms is Θ(n log n). The base of the logarithm does not matter (it differs only by a constant).

### Proof intuition via a decision tree

1. Any comparison sort is a sequence of questions of the form "a[i] ≤ a[j]?". Its work can be represented as a binary decision tree, where each node is a comparison and each leaf is a final ordering.
2. The number of distinct inputs (permutations) is n!, so there must be at least n! leaves.
3. A binary tree with L leaves has a depth of at least log2 L, so the depth is ≥ log2(n!). This is exactly the minimum number of comparisons in the worst case.
4. By Stirling's formula: log2(n!) ≈ n log2 n − 1.44n + O(log n). So the lower bound is Ω(n log n).

### Model assumptions (why this holds)

- We count only key comparisons; each comparison operation yields at most 1 bit of information.
- The keys are arbitrary and unstructured (they cannot be "bucketed" without comparisons).
- The RAM model, with equal cost for elementary operations.

### When you can go faster than O(n log n)

- Counting sort: O(n + k), where k is the size of the range of integer keys. Requires the keys to be small integers (for example, from [0, k)).
- Radix sort: O(n · d) in the number of digits (or O(n log_k U) for base k and range U), works for fixed-length keys/digits (fixed-length strings, 32/64-bit integers).
- Bucket sort: expected O(n) with a "good" data distribution (for example, uniform on [0,1)).
- Summary: linear sorting is possible when we exploit the structure of the keys (a bounded range, fixed length, assumptions about the distribution). In the general case, without these assumptions, it is not possible.

### Practical algorithms and their complexities

- Merge sort: O(n log n) worst case, stable, but requires O(n) extra memory.
- Heap sort: O(n log n) worst case, almost in-place, unstable, worse constants/locality.
- Quick sort: average O(n log n), worst case O(n^2) (see random pivots/median-of-three to reduce the risk), in-place, excellent cache locality.
- Timsort (in Python/Java): worst case O(n log n), adaptive: can be close to O(n) for nearly sorted data.

### Code example: O(n log n) sort (Merge Sort, JS)

```javascript
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);
    else res.push(b[j++]);
  }
  return res.concat(a.slice(i), b.slice(j));
}

// Usage example:
// const arr = [5, 1, 4, 2, 8];
// console.log(mergeSort(arr)); // [1, 2, 4, 5, 8]
```

### Code example: O(n) with a bounded range (Counting Sort, JS)

```javascript
function countingSort(arr, min, max) {
  const k = max - min + 1;
  const count = new Array(k).fill(0);

for (const x of arr) {
    if (x < min || x > max) throw new Error('key out of range');
    count[x - min]++;
  }

let idx = 0;
  for (let i = 0; i < k; i++) {
    while (count[i]-- > 0) arr[idx++] = i + min;
  }
  return arr;
}

// Usage example:
// const arr = [5, 1, 4, 2, 8, 2];
// console.log(countingSort(arr, 0, 10)); // [1, 2, 2, 4, 5, 8]
// Important: works efficiently when (max - min) = O(n).
```

### Summary

- A general-purpose comparison sort cannot be faster than Θ(n log n) - this is an information-theoretic lower bound.
- Linear sorting algorithms are possible only under additional assumptions about the keys or their distribution.
- In practice, choose the algorithm based on the task's constraints: key range, stability, memory, data distribution.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts762 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.