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 Velloreth
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
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(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.
| Language | Algorithm | Notes |
|---|---|---|
| JavaScript (V8) | Timsort | Stable since ES2019 |
| Python | Timsort | Stable, exploits existing runs |
| Java (objects) | Timsort | Stable |
| Java (primitives) | Dual-pivot quicksort | Not stable, faster |
C++ std::sort | Introsort | Quicksort + heapsort + insertion |
| Rust | Pattern-defeating quicksort | Adaptive, detects patterns |
| Go | Pattern-defeating quicksort | Since 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.