Sorting Algorithms Comparison Table — Complexity, Stability, In-Place, and When to Use Each

Every interview candidate can name three sorting algorithms; fewer can defend "why quicksort over merge sort", and fewer still know which sort their language reaches for by default. This reference is the tie-breaker: complexity, stability, in-place, plus the per-language default that decides what happens when you call sort() without thinking.

The master table

*Quicksort's O(log n) space is the recursion depth on balanced pivots; worst case O(n) on bad pivots. k = number of distinct values (counting), key length (radix), or bucket count (bucket). Adaptive = runs faster on partially-sorted inputs.

What the language reaches for by default

You almost never write a sort by hand in interviews. You call the language's built-in, which picks one of the algorithms above. Knowing which one earns credit.

Two consequences worth naming:

• Python and JavaScript sort with Timsort — the same algorithm, O(n log n) worst case, stable. When an interviewer asks "what's the complexity of list.sort?", the answer is O(n log n) worst case, not "O(n log n) average".
• Java's Arrays.sort(int[]) is a rare O(n²) worst-case default. For adversarial inputs on primitive int arrays, box to Integer[] for Timsort's guarantee. This is a niche interview detail but a real footgun.

When to reach for each algorithm

You'll almost always call the language default. Reach for a specific algorithm when the default's guarantees don't match the problem.

Timsort (Python list.sort, Java Collections.sort, JS/Rust default)

Reach for it: always, unless you have a reason not to. O(n log n) worst case, stable, adaptive to partially-sorted inputs (an already-sorted input runs in O(n)). The reason it's the default in three major languages: it's rarely the wrong choice.

Heapsort

Reach for it when: you need in-place sorting with O(1) auxiliary space, guaranteed O(n log n). The only comparison sort with both properties. Slower in practice than Timsort or IntroSort by a constant factor (worse cache behaviour), but wins on space constraints. Interviewers occasionally require it.

Quicksort

Reach for it when: you need in-place, average O(n log n) is enough, and you're happy to accept O(n²) worst case. Quicksort's constant factor is legendarily small on real hardware — cache-friendly, few writes, small code. It's what C++'s std::sort builds on (with a heapsort fallback for the O(n log n) guarantee — that's IntroSort). For pure interview-side code, it's rarely the right answer over Timsort or heapsort.

Merge sort

Reach for it when: you need stable O(n log n) worst case with predictable performance, and O(n) auxiliary space is acceptable. Standard for external sorting (sorting data larger than memory). In interviews, useful for the "sort a linked list in O(n log n) time and O(1) space" variant — merge sort on a linked list is genuinely in-place with only stack space overhead.

Counting sort

Reach for it when: values are integers in a small, known range. O(n + k) time, O(k) space where k = range. If sorting bytes (k = 256), ASCII characters (k = 128), or ages (k ≈ 120), counting sort beats any comparison sort. Falls apart when k grows with n.

Radix sort

Reach for it when: values are fixed-width integers or strings. O(n · k) time where k = number of digits or characters. Beats comparison sorts asymptotically because it dodges the Ω(n log n) comparison-sort lower bound — it doesn't compare, it distributes. Rarely the interview-preferred answer because implementations are longer than the alternative, but knowing to name it earns credit on "how do you sort 10⁹ integers in linear time?".

Insertion sort

Reach for it when: n is small (< 50) or the input is nearly sorted. O(n) on already-sorted inputs. It's what Timsort and IntroSort delegate to for small partitions internally. Rarely a standalone answer, but often a component.

Bubble and selection

Reach for them: never in interviews. Bubble is educational; selection is worse than insertion in every dimension except memory writes (which almost never matters). Both are useful for teaching the concept of a sort; neither is anyone's first choice for a real problem.

Stability — what it means and when it matters

A sort is stable if equal-valued elements preserve their relative input order. In interview code, stability matters when:

• Sorting by a secondary key after sorting by a primary key. Sort by age first, then by name; the age-order is preserved among equal names.
• Rebuilding an output where equal elements need their original order for correctness. Emitting logs sorted by timestamp where two events with equal timestamps should stay in file order.
• Tuple-key sorts you spelled as two passes. If either pass isn't stable, the second pass shuffles equal-key groups.

If stability doesn't matter — you're sorting numbers, or the equal-key order is unimportant — you can use unstable sorts freely.

In-place — what it means

In-place sorts use O(1) auxiliary space (or O(log n) for the recursion stack). Heapsort is in-place; merge sort is not (needs O(n) auxiliary). Timsort is technically not in-place either — it uses O(n) auxiliary in the worst case, though usually less.

Interviewers rarely require in-place unless the problem specifies it. When they do, heapsort is the safe answer.

Adaptive — the "already sorted" bonus

An adaptive sort runs faster on partially-sorted inputs. Timsort is exceptionally adaptive — it detects "runs" (already-sorted stretches) and merges them, giving O(n) on already-sorted input and much better than O(n log n) on inputs with detectable structure. Insertion sort is adaptive in the same direction.

Quicksort, heapsort, and merge sort are not adaptive — they do the same O(n log n) work regardless of input structure.

Non-comparison sorts and the Ω(n log n) lower bound

Any sort that decides ordering purely by comparing two elements is bounded below by Ω(n log n). That's the reason quicksort, merge sort, Timsort, and heapsort can't be asymptotically better.

Counting, radix, and bucket sort break this bound by not comparing — they distribute elements by value. They can hit O(n) or O(n · k) at the cost of assumptions about the input (small range, fixed-width representation).

If an interviewer asks "sort n numbers in the range 0, k in linear time", the expected answer is counting sort. If they say "sort n 32-bit integers", the answer is radix sort. If they say "sort n arbitrary comparable objects", you're back to Timsort.

Common bugs in "which sort" claims

• "Quicksort is O(n log n)." Average case, yes. Worst case is O(n²). If the interviewer asks for worst-case, name it.
• "Merge sort is O(n log n) space." No — it's O(n) auxiliary. O(log n) is the recursion depth (which is a component), but the merge buffer dominates.
• "Timsort is O(n log n) average." Timsort's worst case is O(n log n). Saying "average" implies "worst is worse", which is wrong.
• "Java's Arrays.sort is stable." Only for Object[]. Arrays.sort(int[]) uses dual-pivot Quicksort and is unstable.
• "Heap sort is O(n log n) time and space." Heapsort is O(n log n) time, O(1) space. That's exactly its selling point.

When to specify a comparator

The default sort compares "naturally" — numeric for numbers, lexicographic for strings. Reach for a comparator when:

• Sorting by a computed key (sorted(items, key=lambda x: x.age) in Python, Comparator.comparingInt(x -> x.age) in Java, (a, b) => a.age - b.age in JS).
• Sorting by multiple keys with different directions (primary asc, secondary desc — tuple keys in Python, chained comparators in Java, expression in JS).
• Sorting strings that should sort as numbers (['10', '2'] — lexicographic gives ['10', '2']; numeric gives ['2', '10']).

Reversing the sort is comparator territory: sorted(nums, reverse=True) in Python, Comparator.reverseOrder() in Java, (a, b) => b - a in JS.

Complexity quick reference

For the amortised claims — Timsort's O(n) on runs, quicksort's O(n²) worst case, heapsort's O(1) space — see the Big-O cheat sheet and the time-complexity-of-common-operations post. For the per-language sort() semantics inline in code, see the Python, Java, and JavaScript cheat sheets.

The patterns this table backs

• The two-pointer pattern begins with a sort; picking the right sort (Timsort in Python, Arrays.sort in Java with the worst-case caveat) is a real detail.
• The binary-search template assumes a sorted input; how you got it there determines the cost of the setup.
• The monotonic-stack pattern avoids sorting entirely — one of its selling points.
• The DP state-definition post sometimes sorts as a preprocessing step for interval DP or greedy hybrids.

The sort you reach for isn't decoration. Naming it — and defending its worst-case bound — is what separates candidates who know their language from those who "call .sort() and hope".