↩ back to Guides

Choosing a Comparison Sort

This site has eleven comparison sorts now — Insertion Sort, Bubble Sort, Selection Sort, Shell Sort, Heap Sort, Quicksort, Merge Sort, Timsort, Introsort, Bitonic Sort, and Cycle Sort — the largest single category on the site, and the one where "which one do I use" is the most ordinary of questions: every one of these sorts an array by comparing pairs of elements, and none of them needs its own page to justify existing before a reader picks. Seven of the eleven are the classic textbook sorts, compared below by the questions that actually decide between them; Timsort, Introsort, Bitonic Sort, and Cycle Sort are the odd ones out. The first two are real production hybrids built from ingredients this page already covers rather than a competing approach in their own right; the third isn't a hybrid at all, it's a different paradigm — a fixed comparator schedule instead of anything the other ten would recognize as an algorithm's control flow. The fourth trades away speed entirely for a property none of the other ten optimize for: the fewest possible writes to the array. All four get their own section instead of being forced into the same funnel.

Three questions, not seven algorithms

In order, cheapest to check first: Is n small, or already nearly sorted? If so, this settles it before anything else below matters. Does the relative order of equal elements need to survive the sort (stability)? Some real sorts — sorting rows by one column while a prior sort already ordered them by another — depend on this and break silently if it's missing. If stability doesn't force the answer, is a worst-case guarantee required, or does typical-case speed matter more? This is the classic heap sort vs. quicksort trade, and it's the last question, not the first, because it only matters once the first two have already been ruled out.

Small or nearly sorted: insertion sort, not bubble sort

Insertion sort is O(n²) worst and average case, but its inner loop bails out the moment it finds the right slot — on already-sorted input that's O(n), and the same adaptivity pays off on any array that's only slightly out of order, no matter how large n is. That's not a special mode you opt into: it falls out of the algorithm's own structure, which is exactly why several production sort implementations (V8's Array.prototype.sort, Timsort) switch to insertion sort for small sub-arrays regardless of what the outer algorithm is.

Bubble sort looks like the same trade at first glance — also O(n²) worst and average, also stable — but its O(n) best case only exists with an explicit early-exit flag bolted on; bubble sort's own pitfalls confirm that without it, an already-sorted 7-element array still runs all 6 passes and 21 comparisons, the same as a worst-case input. Insertion sort gets its adaptivity for free from the inner loop's own condition; bubble sort has to be told to look for it. There's no input where bubble sort is the better choice over insertion sort — its page exists to make that contrast concrete, not because it's a live candidate.

Stability required, and n isn't small: merge sort

Stability rules out more of the seven than it might seem. Selection sort's long-range swap can jump one equal element clean over another — confirmed on the tagged pair [3♥, 5, 3♦, 1], which comes out [1, 5, 3♦, 3♥], order flipped. Shell sort loses stability the moment a gap exceeds 1, since it compares elements that aren't adjacent and can leapfrog an equal one sitting between them. Heap sort's sift-down swaps and quicksort's partition swaps both move elements long distances with no tie-breaking rule. That leaves insertion sort, bubble sort, and merge sort — and once n is past the range where insertion sort's quadratic worst case is a real cost, merge sort is the one built for scale: a deliberate <= in its merge step keeps left-half elements ahead of equal right-half elements, preserving original order, while still guaranteeing O(n log n) in every case — best, average, and worst alike. The cost is O(n) extra space for the merge buffers, unlike every other sort on this page. That combination — stable, guaranteed n log n, no quadratic worst case — is why merge sort (or a hybrid built on it, like Timsort, covered in its own section below) backs the stable sort in most standard libraries.

Stability not required: heap sort's guarantee vs. quicksort's speed

Once stability is off the table, the choice comes down to a guarantee against typical-case speed. Heap sort is O(n log n) in every case — no adversarial input pushes it worse, because extracting from a heap costs O(log n) regardless of the array's original order — at O(1) extra space. Quicksort is O(n log n) only on average; this site's last-element pivot rule degrades to O(n²) on an already-sorted or reverse-sorted array, confirmed directly by pasting 1,2,3,4,5,6,7,8 into its own demo. Randomized or median-of-three pivots make that worst case unlikely to hit by accident, but neither eliminates it — quicksort's own pitfalls are explicit that "strong practical default" and "asymptotically solved" are different claims. In exchange, quicksort partitions in place with better cache locality than heap sort's far-apart sift-down jumps, and is typically faster in practice despite the weaker guarantee.

Real standard-library sorts mostly refuse to pick just one of these three. Introsort — behind C++'s std::sort — runs quicksort by default, falls back to heap sort only once recursion depth signals a bad pivot pattern, and switches to insertion sort below some small n for the same reason as the previous section. The three sections above aren't really competing answers; they're the ingredients a hybrid picks between at different sizes and different moments, and this site's own pages implement each ingredient standalone specifically so each one can be read and verified on its own. Introsort's own page is where that recursion-depth switch is built and made to actually fire, rather than just described; Timsort, covered next, is this site's other worked example of the same pattern — a hybrid built from ingredients this guide already covers.

Two niche picks: selection sort's write count, shell sort's middle ground

Selection sort always makes exactly n(n-1)/2 comparisons no matter the input — no adaptive best case at all — but at most n - 1 swaps total, one per pass, and often fewer. That's the one real reason to reach for it: when writes are far more expensive than comparisons (flash memory wear leveling, large records with a cheap-to-compare key), selection sort's write count is bounded by how many elements are actually out of place, a guarantee none of the other six on this page make.

Shell sort generalizes insertion sort by shifting at wide gaps before narrowing to a final gap-1 pass, trading some of insertion sort's quadratic risk for a sequence-dependent worst case — this site's halving sequence still degrades to O(n²) on an adversarial input, and no known gap sequence has a proven O(n log n) bound, only better empirical or amortized ones (Hibbard's reaches O(n^1.5)). It sorts in place at the same O(1) space as insertion and heap sort, without heap sort's cache-unfriendly jumps or merge sort's buffer — a real middle ground, but an unproven one, which is exactly why shell sort's own page describes its reputation as "good enough, rarely the right choice when something else is available."

The eighth entry: Timsort doesn't compete in the funnel above, it's built from it

Timsort isn't a candidate answer to the three questions at the top of this page — it's what you get by taking "stability required, n isn't small" seriously and then also checking whether the input has real-world structure before doing merge sort's full O(n log n) work regardless. It detects existing ascending or descending stretches (natural runs), extends short ones with binary-insertion sort, and merges the rest with the same balance-preserving discipline that gives merge sort its guarantee. On an already-sorted 1,000-element array it does the whole job in 1,000 comparisons to merge sort's 4,932, measured, not estimated — and on data with no structure at all, or disorder scattered too thin for run detection to notice, it's measurably no better than merge sort, sometimes very slightly worse. It's the site's one production-grade hybrid with its own page instead of just a mention, exactly because that adaptivity is a real, checkable claim rather than a description of one.

The ninth entry: Introsort, a different hybrid built from three of the others

Introsort — behind C++'s std::sort — is also not a candidate answer to the three questions above; it's what "typical-case speed matters more than a worst-case guarantee," the answer the unstable section gives quicksort, looks like once someone also insists on a guarantee for the rare case quicksort gets unlucky. It runs quicksort by default, counts its own recursion depth as it goes, and falls back to heap sort — for whichever range triggered it, not the whole array — the moment that count passes 2 · floor(log2(n)), a threshold that scales with input size rather than a fixed constant. Below a small range size it switches to insertion sort instead, for the unrelated reason the niche-picks section already gives it: recursion overhead costs more than a few shifts once a range is small enough. Where Timsort combines two ingredients toward one goal (stability, kept cheap when the input already has structure), Introsort combines three toward a different one: quicksort's average speed, with heap sort's guarantee as a safety net that measurably almost never fires — zero times in 1,000 seeded trials on shuffled data, but reliably once on the exact adversarial input that breaks plain quicksort, both measured on Introsort's own page.

The tenth entry: Bitonic Sort trades total work for a fixed schedule

Bitonic Sort doesn't answer any of the three questions above either, but for a different reason than Timsort or Introsort: it isn't trying to win on typical-case speed, an adaptive best case, or even a matching worst-case bound — the five entries built for exactly that (heap sort, quicksort, merge sort, Timsort, Introsort) all reach O(n log n) or better on average, and Bitonic Sort's O(n log² n) total comparator count is strictly worse than any of them. What it buys instead is a property none of the other ten have: the exact sequence of index pairs it compares is fixed by the array's length alone, computed before a single element is inspected, and measured identical — not just similar — across sorted, reverse-sorted, and random input of the same size (24 comparators at n=8, every time, on Bitonic Sort's own page). That's the one property every other sort on this page actively works against: quicksort's partition, Timsort's run detection, and insertion sort's adaptive inner loop all change their behavior based on what they find, which is exactly what makes them unsuitable for hardware where every parallel lane has to execute the same instruction stream regardless of the data it's holding.

The eleventh entry: Cycle Sort trades speed for guaranteed-minimal writes

Cycle Sort shares Bitonic Sort's shape of answer — it isn't competing in the funnel above either — but optimizes for a completely different resource. Where Bitonic Sort spends extra comparisons to buy a fixed schedule, Cycle Sort spends nothing extra on comparisons at all (it's O(n²), the same floor selection sort sits at) and instead minimizes writes: every element lands in its final array slot at most once, the provable minimum for any in-place comparison sort, measured directly against selection sort on the same inputs on Cycle Sort's own page (selection sort wrote strictly more in 98.2% of 3,000 trials, never fewer). None of the other ten entries on this page even track writes as a separate cost from comparisons — Cycle Sort is the only one for which the distinction is the entire point.

Side by side

Race them yourself

The table above is asymptotic notation — worth seeing the actual numbers behind it. This runs the exact reference implementation from each of the eleven pages above, unmodified, in your own browser, on one randomly generated array shared across all eleven, timed with performance.now(). It's not a rigorous benchmark — JIT warmup, garbage collection, and whatever else your browser is doing all add noise — but the gap between O(n log n) and O(n²) shows up clearly enough at a few thousand elements that the noise doesn't matter. Watch Bitonic Sort specifically: it registers as the slowest or near-slowest entry at every size and every data pattern, not a fluke but the direct, measured consequence of the extra total comparators the section above already names — and it's the one entry whose time doesn't move at all when you switch data to already sorted or reverse sorted, for the same reason. Cycle Sort's time moves the opposite way selection sort's does: selection sort's cost is a function of n alone, flat across every pattern, while Cycle Sort gets measurably slower from sorted to reverse-sorted to random — sorted data needs zero of the position-recomputing rescans that fire on every displaced element, so it's the one pattern where Cycle Sort's own extra bookkeeping mostly disappears.

Switch data to already sorted at 5,000 elements and watch quicksort specifically: its reference implementation uses a last-element pivot with no randomization, so on that adversarial input its recursion depth runs n deep instead of log n — the exact pitfall the section above describes, now timed instead of just claimed. Introsort runs the identical partition scheme on the same input but doesn't melt down with it: at n = 5,000 its depth counter reaches zero after only 24 levels (2 · floor(log2(5000))), at which point the remaining ~4,976-element range gets handed to heap sort instead of another partition — visibly the fastest or near-fastest entry on this exact input that breaks quicksort, not by luck but by the same mechanism Introsort's own Pitfalls section measures directly. Insertion sort and bubble sort do the opposite: both drop to sub-millisecond, insertion sort's adaptive inner loop and bubble sort's early-exit flag each paying off at once. Switch to reverse sorted and insertion and bubble sort become the slow ones instead — every element is as far from its final slot as it can be, so neither algorithm's best case triggers. Timsort matches insertion and bubble sort's speed on both sorted patterns for a different reason than either of them — not an adaptive inner loop or an early-exit flag, but run detection finding the whole array is already one run and skipping the merge phase entirely, exactly as measured on Timsort's own page.

None of these eleven beat O(n log n) — they can't (or, for Bitonic Sort and Cycle Sort, don't even try to), because every one of them is built entirely out of "is A bigger than B?" comparisons, and that's a proven floor for any sort that only asks that question. Non-Comparison Sorts escapes the bound instead of beating it, by never comparing elements at all — counting occurrences or reading digits instead — worth a look once this page's guarantee starts to feel like a hard floor rather than one family's tradeoff.

This started as the site's third guide, comparing seven textbook comparison sorts by the questions that decide between them; Timsort joined later as an eighth entry and a different kind of answer — not one more competing option in the funnel above, but a real hybrid built from two of the other seven, with its own page and its own measured numbers rather than just a mention. Introsort joined as a ninth entry the same way — a different hybrid, built from three ingredients instead of two, aimed at a guarantee rather than adaptivity. Bitonic Sort joined as a tenth entry and a different kind of answer again — not a hybrid of anything already here, but a fixed comparator network with no data-dependent branching at all, trading total work for exactly the property every other entry on this page treats as an optimization opportunity. Cycle Sort joined as an eleventh entry and yet another different kind of answer — not a hybrid, not a fixed network, but a different metric entirely: the fewest possible writes instead of the fewest possible comparisons. See the journal for session notes on all five.