Why is "quicksort, it's the fastest" a weak answer to a sorting question?
answer
- start by asking about the data
- size, existing order, ties, keys, memory
- what the default library sort already does
- quicksort trades guarantees for average speed
- stability and space are requirements, not tastes
basics
~20 sQuicksort is fast on average but not universally best: it is unstable and degrades toward O(n^2) with naive pivots. The defensible answer is the standard library sort, chosen after asking about size, existing order, stability needs, key type and memory.
solid answer
~50 sThe answer is weak because it names an algorithm before establishing the input. A sorting choice is driven by five properties: how many elements, whether the data is already partly ordered, whether records with equal keys must keep their relative order, what the keys look like (bounded integers and fixed-width keys open up counting and radix sorts), and how much auxiliary memory you are allowed. The correct default in almost every real system is the standard library sort, because it is a tuned hybrid: insertion sort on small runs, a fallback that caps the worst case at O(n log n), and often run detection for presorted data. You override that default only for a concrete reason — a hard worst-case guarantee, an O(1)-auxiliary-space rule, or key structure that makes a non-comparison sort legitimate. Quicksort itself is genuinely excellent: in-place, cache-friendly, small constants — but unstable, and quadratic in the worst case.
go deeper
Be ready to say the default out loud — the standard library sort — and then name two or three input properties that would change it: size, whether ties must keep their order, and how much extra memory you may use.
Explain the mechanics behind the default: why hybrids drop to insertion sort on small runs, why a depth-limited fallback exists at all, and what quicksort actually trades away (stability and its worst case) for locality and in-place operation.
Show you turn a vague ask into requirements. Interviewers expect you to ask about presortedness, key type, tie semantics and the memory ceiling before committing, then defend the pick against the one property that would flip it.
Own the position that the default is the default for organisational reasons too: a bespoke sort is code the team maintains and fuzz-tests forever. Argue deviations from measured evidence — a latency budget, a memory ceiling, a key shape — not from elegance.
## What the question is actually testing An interviewer who asks "how would you sort this?" is rarely testing whether you can recite partitioning. They are testing whether you treat sorting as a *choice under constraints* or as a memorised fact. Naming one algorithm instantly says you have one tool. The strong move is to state the default, name the properties that would change it, and then commit to a choice. ## The five properties that decide the answer 1. **Size (n).** At n in the tens, everything is fast and simplicity wins — this is exactly why tuned library sorts fall back to insertion sort on short runs. Asymptotic superiority promises nothing at small n; constants dominate there. 2. **Existing order.** If the data is nearly ordered, adaptive algorithms approach linear time, while a quicksort with a first-element or last-element pivot hits its worst case on precisely that input. 3. **Stability requirement.** Stability means records with **equal keys** keep their relative input order. It matters only when equal elements are distinguishable — sorting bare numbers gains nothing from it; sorting records by one field while an earlier ordering must survive depends on it entirely. 4. **Key type and range.** Comparison sorts are bounded below by Omega(n log n) comparisons in the worst case. Counting, radix and bucket sorts escape that bound by not comparing — but only when keys are bounded integers, fixed-width byte strings or otherwise mappable to positions, and they pay for it in auxiliary memory proportional to the key range or a per-pass buffer. 5. **Memory ceiling.** The standard array form of merge sort needs O(n) extra space. Heapsort sorts in place with an O(n log n) worst case but poor locality and no stability. Recursion depth counts as space too: a recursive quicksort with unlucky pivots can push O(n) frames. ## A compact property table | Algorithm | Worst case | Stable | Auxiliary space | Adaptive to order | |---|---|---|---|---| | Merge sort (array form) | O(n log n) | yes | O(n) | only if run-detecting | | Quicksort | O(n^2) | typically no | O(log n) stack (expected) | no | | Heapsort | O(n log n) | no | O(1) | no | | Insertion sort | O(n^2) | yes | O(1) | strongly | | Counting / radix | O(n + k) / O(n·w) | can be | O(n + k) / O(n) | no | Read the table as a menu of *guarantees*, not a ranking. Big-O is an upper bound: labelling quicksort O(n^2) does not claim it behaves quadratically on your data, and labelling merge sort O(n log n) does not make it faster than quicksort on a random array — usually it is not. ## Why the library sort is the right default Production sorts are not textbook algorithms. They are hybrids refined over decades: a partitioning or merging core, insertion sort below a size threshold, and a guard that prevents the pathological path. That is a lot of engineering you get for free, and it is why "call the standard sort" is a *correct* answer, not a lazy one. Mainstream runtimes diverge here in a way worth knowing: the default object sorts in Java and Python are stable adaptive merge hybrids, while those in C++ and Go are unstable hybrids that begin with quicksort-style partitioning and fall back to a guaranteed O(n log n) algorithm when recursion runs deep. Same problem, different default on stability — which tells you stability is a *choice* the platform made for you, and one you must verify rather than assume. ## When "call the standard sort" stops being right - **A hard worst-case guarantee.** A tail-latency budget on adversarially shaped input pushes you toward an algorithm whose worst case is O(n log n), or a hybrid that provably falls back. - **A strict auxiliary-space rule.** An O(1)-space constraint rules out the classic merge-sort buffer. - **Key structure.** Millions of records keyed by a small bounded integer, or by fixed-width byte keys, are counting/radix territory — linear in n with a modest number of passes. - **You do not need a full sort at all.** If the goal is the k largest or a median, sorting everything is the wrong shape of work. ## What a strong answer sounds like "Default: the standard library sort. Before I commit, I want to know n, whether the data is already partly ordered, whether ties must keep their input order, whether the keys are bounded integers, and what my memory ceiling is. Given a few million wide records with a stability requirement and no memory pressure, I stay with the stable library sort; given a hard O(1)-space rule I take an in-place O(n log n) algorithm and accept losing stability." That answer takes fifteen seconds and demonstrates everything a single algorithm name hides.
- What does a production standard sort do that a textbook quicksort does not?It is a hybrid. Short runs go to insertion sort, where the constants win; a depth limit or explicit fallback caps the worst case at O(n log n) instead of leaving a quadratic path open; many implementations detect already-ordered runs and merge them rather than resorting. On top of that sit years of constant-factor tuning and enormous test exposure — none of which you reproduce in an afternoon.
- Name a case where you would legitimately not call the standard library sort.Three: keys that are bounded small integers or fixed-width byte strings at large n, where a counting or radix pass is linear and the comparison sort is not; a hard rule of O(1) auxiliary space, which rules out the standard merge buffer; and data that simply does not fit in memory, which is a different family of algorithm entirely rather than a different comparator.
- Why is quicksort still so widely used given its O(n^2) worst case?Because the worst case is avoidable and the average case is excellent. It sorts in place with only O(log n) expected stack, partitions sequentially so it is very cache-friendly, and has small constants. A randomized or sampled pivot makes the quadratic case improbable rather than input-triggered, and a depth-limited fallback to a guaranteed O(n log n) algorithm removes it as a risk outright.
Naming quicksort before asking about the data is like naming a vehicle before asking whether the cargo is a letter or a sofa.
saying these in an interview costs you the question
- Quicksort is always the fastest sorting algorithm
- All sorts are O(n log n), so the choice does not matter
- Stability is a nice-to-have, not a real requirement
- Big-O is the only thing that decides the choice
- Hand-rolling a sort shows more skill than calling the default