Skip to content
Velloreth
Programming 10 min read

Sorting Algorithms Compared: Which One and Why

Compare bubble, insertion, merge, quick, heap and counting sort on time, space and stability, and learn which one your language actually uses.

By

The lower bound you cannot beat

Before comparing algorithms, it is worth knowing the wall they all hit.

Any sorting algorithm that works by comparing pairs of elements needs at least O(n log n) comparisons in the worst case. This is not a limitation of current techniques; it is a proven lower bound. The argument is information-theoretic: there are n! possible orderings, each comparison gives one bit of information, and you need at least log₂(n!) ≈ n log n bits to distinguish them.

So merge sort and heapsort are not merely good — they are optimal among comparison sorts. Any improvement has to come from not comparing, which is what counting and radix sort do.

The comparison sorts

AlgorithmBestAverageWorstSpaceStable
BubbleO(n)O(n²)O(n²)O(1)Yes
InsertionO(n)O(n²)O(n²)O(1)Yes
SelectionO(n²)O(n²)O(n²)O(1)No
MergeO(n log n)O(n log n)O(n log n)O(n)Yes
QuickO(n log n)O(n log n)O(n²)O(log n)No
HeapO(n log n)O(n log n)O(n log n)O(1)No

Bubble sort

Repeatedly swap adjacent elements that are out of order.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
  return arr;
}

Bubble sort is the one everyone learns first and nobody uses. It is O(n²) with a large constant, and its only virtue is that it is easy to explain. The swapped flag gives it O(n) on already-sorted input, which is the one case where it is not terrible.

Use it: never, except to teach the concept.

Insertion sort

Build a sorted prefix by inserting each new element into its correct place.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

Insertion sort is O(n²) but has a tiny constant and is O(n) on nearly-sorted data. That combination makes it genuinely useful: it is the base case in almost every production sort.

When a subarray gets small enough — typically 16 to 32 elements — the overhead of recursion and merging outweighs the asymptotic advantage, and insertion sort wins. Timsort, used by Python and V8, does exactly this.

Use it: for small arrays, nearly-sorted data, and as the base case of a hybrid sort.

Selection sort

Find the minimum of the unsorted portion and swap it into place.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    [arr[i], arr[min]] = [arr[min], arr[i]];
  }
  return arr;
}

Selection sort always does exactly n²/2 comparisons regardless of input, so it has no best case. Its one advantage is that it performs at most n swaps, which matters when writes are far more expensive than reads — writing to flash memory, for example.

Use it: when swap cost dominates, which is rare.

Merge sort

Divide the array in half, sort each half, then merge the sorted halves.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    out.push(a[i] <= b[j] ? a[i++] : b[j++]); // <= keeps it stable
  }
  return out.concat(a.slice(i), b.slice(j));
}

Merge sort guarantees O(n log n) in every case, is stable, and is easy to reason about. Its cost is O(n) extra space for the merged output.

The <= in the merge is what makes it stable. Using < would take from the right half on ties and reverse equal elements.

Merge sort is the sort of choice when you need predictable performance or stability, and it is the basis of external sorting — sorting data too large for memory by merging sorted runs from disk.

Use it: when you need guaranteed O(n log n), stability, or external sorting.

Quicksort

Pick a pivot, partition the array so smaller elements come before it and larger after, then recurse on both sides.

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low >= high) return arr;
  const p = partition(arr, low, high);
  quickSort(arr, low, p - 1);
  quickSort(arr, p + 1, high);
  return arr;
}

function partition(arr, low, high) {
  // median-of-three pivot reduces worst-case risk
  const mid = low + Math.floor((high - low) / 2);
  if (arr[mid] < arr[low]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[high] < arr[low]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[high] < arr[mid]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
  [arr[mid], arr[high - 1]] = [arr[high - 1], arr[mid]];

  const pivot = arr[high - 1];
  let i = low;
  for (let j = low; j < high - 1; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[high - 1]] = [arr[high - 1], arr[i]];
  return i;
}

Quicksort is in-place, has excellent cache behaviour, and is usually the fastest comparison sort on random data. Its weakness is the worst case: if the pivot is always the extreme element, each partition removes only one element and the recursion is O(n) deep, giving O(n²).

The fix is pivot selection. Random pivots make the worst case vanishingly unlikely. Median-of-three — taking the median of the first, middle, and last elements — handles already-sorted input, which is the case that breaks naive implementations.

Use it: when you want the fastest average performance and can tolerate the worst case, or when memory is tight.

Heapsort

Build a max-heap, then repeatedly extract the maximum.

function heapSort(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(arr, i, n);
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    siftDown(arr, 0, i);
  }
  return arr;
}

function siftDown(arr, i, n) {
  while (true) {
    let largest = i;
    const l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest === i) return;
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}

Heapsort gives O(n log n) in every case with O(1) extra space — the only sort with both guarantees. Its problem is cache behaviour: the heap jumps around memory, so it is consistently slower than quicksort in practice despite the better worst case.

Use it: when you need guaranteed O(n log n) and cannot afford O(n) extra space.

The non-comparison sorts

These break the O(n log n) barrier by exploiting the structure of the keys rather than comparing them.

Counting sort

Count occurrences of each value, then reconstruct the sorted output.

function countingSort(arr, max) {
  const counts = new Array(max + 1).fill(0);
  for (const n of arr) counts[n]++;
  const out = [];
  for (let v = 0; v <= max; v++) {
    for (let c = 0; c < counts[v]; c++) out.push(v);
  }
  return out;
}

Counting sort runs in O(n + k) where k is the range of values. It is linear when k is comparable to n, and wasteful when k is huge — sorting a million values in the range 0 to 10⁹ would need a billion counters.

Use it: for integers in a known, small range — ages, grades, byte values, test scores.

Radix sort

Sort digit by digit, from least significant to most significant, using a stable sort for each pass.

function radixSort(arr) {
  let max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingSortByDigit(arr, exp);
  }
  return arr;
}

Radix sort is O(d × n) where d is the number of digits. For fixed-width integers, d is a constant, so it is effectively O(n). It requires a stable subroutine, which is why counting sort is used for each pass.

Use it: for fixed-width integers or strings, especially in large batches.

What your language actually uses

No production library implements a single textbook algorithm. They use hybrids.

LanguageAlgorithmNotes
JavaScript (V8)TimsortStable since ES2019
PythonTimsortStable, exploits existing runs
Java (objects)TimsortStable
Java (primitives)Dual-pivot quicksortNot stable, faster
C++ std::sortIntrosortQuicksort + heapsort + insertion
RustPattern-defeating quicksortAdaptive, detects patterns
GoPattern-defeating quicksortSince Go 1.19

Timsort is the most interesting of these. It scans for existing ascending and descending runs, reverses the descending ones, and merges runs of at least a minimum length. On real-world data, which is often partially ordered, it approaches O(n).

Introsort takes a different approach: it starts with quicksort, tracks recursion depth, and switches to heapsort if the depth exceeds 2 log n — guaranteeing O(n log n) worst case while keeping quicksort’s average speed.

Stability, and why it matters

A stable sort preserves the relative order of elements that compare equal. This matters whenever you sort by multiple keys.

Suppose you have a list of people and you want them sorted by age, with names alphabetical within each age. The idiomatic approach is to sort by name first, then by age:

people.sort((a, b) => a.name.localeCompare(b.name));
people.sort((a, b) => a.age - b.age); // stable, so names stay sorted

This only works if the second sort is stable. With an unstable sort, the name ordering is destroyed.

JavaScript’s sort is stable as of ES2019, so this pattern is safe. In older engines it was not, and the pattern silently produced wrong results.

Practical guidance

  • Use your language’s built-in sort. It is a tuned hybrid that will beat anything you write.
  • Sort once, not repeatedly. If you sort inside a loop, hoist it out.
  • Provide a comparator that is consistent. A comparator that returns inconsistent results for the same pair can cause undefined behaviour or crashes in some engines.
  • Prefer a key function over a complex comparator when your language supports it, for clarity.
  • Consider whether you need a full sort. If you only need the top k, a heap is O(n log k) instead of O(n log n).
  • Watch out for sorting objects by reference. Sorting mutates in place; copy first if the original order matters.

For the complexity notation behind these tables, see Big-O notation explained. For the structures that make heaps and merges possible, data structures every developer should know and binary search explained — sorting and searching are usually paired.

Quotable summary

Comparison-based sorting has a proven lower bound of O(n log n), so merge sort and heapsort are optimal in the worst case. Merge sort is stable and guarantees O(n log n) at the cost of O(n) space; quicksort is in-place and usually fastest but degrades to O(n²) on bad pivots; heapsort guarantees O(n log n) with O(1) space but has poor cache behaviour. Insertion sort is O(n²) yet wins on small or nearly-sorted arrays, which is why production libraries use it as a base case. Counting and radix sort beat O(n log n) by not comparing elements, but only apply to integers or fixed-width keys. Real libraries use hybrids — Timsort in Python and JavaScript, introsort in C++, pattern-defeating quicksort in Rust and Go.

Frequently asked questions

Which sorting algorithm is the fastest?
There is no single answer. Quicksort is usually fastest on random data in practice, merge sort is more predictable, and insertion sort wins on small or nearly-sorted arrays. Real libraries combine several, which is why they are called hybrid sorts.
What is the fastest possible sorting algorithm?
For comparison-based sorting, O(n log n) is a proven lower bound, so no algorithm can do better in the worst case. Counting sort and radix sort beat it by not comparing elements, but they only apply to integers or fixed-width keys.
What does it mean for a sort to be stable?
A stable sort preserves the relative order of elements that compare equal. If you sort a list of people by name and then by age, a stable sort keeps the names alphabetical within each age group. An unstable sort may scramble them.
Why is quicksort O(n²) in the worst case?
Because if the pivot is always the smallest or largest element, each partition splits off only one element, giving n levels of recursion instead of log n. This happens on already-sorted input with a naive first-element pivot, which is why real implementations randomise or use median-of-three.
Which sorting algorithm does JavaScript use?
JavaScript's Array.prototype.sort is required to be stable since ES2019. V8 uses Timsort, a hybrid of merge sort and insertion sort, which is stable and performs well on partially sorted data.
When should I use counting sort?
Use counting sort when you are sorting integers within a known, reasonably small range, such as ages, grades, or byte values. It runs in O(n + k) time where k is the range, so it is only faster when k is comparable to n.