You will almost never hand-write a sort in production. Whatever ships with your language beats what you’d type under time pressure, and reaching for it is the correct instinct. Interviewers keep asking about sorting anyway, because a five-minute conversation about it exposes whether you understand time and space tradeoffs, what stability buys you, and why every comparison sort runs into the same wall around n log n.
The skill being tested is knowing which one to name when the constraints shift. Nearly-sorted input, a hard memory budget, billions of rows that don’t fit in RAM, keys drawn from a small range: each points at a different answer, and a strong candidate says why.
Time, space, and stability for every sort worth knowing
Read the worst-case column first. That’s the one that bites in production, and the one an interviewer will press on.
| Algorithm | Best time | Average time | Worst time | Extra space | Stable | Reach for it when |
|---|---|---|---|---|---|---|
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Small or nearly-sorted arrays; the finisher inside faster sorts |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Almost never; only when a write costs far more than a read |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Stability matters, linked lists, or data too big for memory |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Default in-memory array sort when average speed wins |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Guaranteed n log n with no extra allocation |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Partly-ordered real data; the default in Python and Java for objects |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | Integer keys in a small, known range k |
| Radix sort | O(w·n) | O(w·n) | O(w·n) | O(n + k) | Yes | Fixed-width integers or strings, w passes over the data |
| Bucket sort | O(n + k) | O(n + k) | O(n²) | O(n) | Depends | Values spread evenly across a known range |
Why n log n is the floor when you compare elements
Any sort that learns about the data only by comparing pairs of elements cannot beat O(n log n) in the worst case, and this isn’t a matter of nobody being clever enough yet. Picture the algorithm walking down a decision tree, one comparison per branch. To sort n distinct items it has to be able to reach any of the n! possible orderings, so the tree needs at least n! leaves. A binary tree with n! leaves has height at least log₂(n!), which works out to about n log n. That height is the comparison count in the worst case.
Merge sort, heapsort, and a well-behaved quicksort already sit at that theoretical limit. The linear-time sorts lower down only get past it by refusing to compare at all, which costs them generality.
Quicksort is fast on average and quietly dangerous
Quicksort is the default in-memory choice for good reason: small constant factors and in-place, cache-friendly operation, since it works on contiguous chunks. The average case is O(n log n), and on real arrays it usually beats merge sort on wall-clock time.
The trap is the pivot. Choose the first or last element as the pivot, feed it an already-sorted array, and every partition peels off exactly one element. That’s n levels of recursion doing O(n) work each, so O(n²), on the input you’d least suspect. Two fixes come up constantly. Randomize the pivot, or take the median of the first, middle, and last elements. Either one makes the pathological case vanishingly unlikely without touching the average behavior.
The second trap is duplicates. A plain two-way partition on an array of mostly-equal keys degrades toward O(n²). The fix is a three-way partition, the Dutch national flag idea, which gathers everything equal to the pivot into a middle band and recurses only on the strictly-smaller and strictly-larger parts. When an interviewer says “the array has a lot of repeated values,” that partition is the phrase they want back.
When merge sort and heapsort earn the pick
Merge sort is stable and its worst case is O(n log n) with no asterisk, which is why you reach for it when order among equal keys has to survive, or when the input is a linked list, where merging needs no random access and fits naturally. It is also the engine of external sorting: when the data won’t fit in memory, sort chunks that do, write the sorted runs to disk, and merge them in a streaming pass. The price is O(n) extra space for the merge, which rules it out under a tight memory budget.
Heapsort is the name to reach for when the constraint reads “guaranteed O(n log n) and O(1) extra space.” It never degrades to quadratic and it allocates nothing. What you give up is stability and cache behavior. Walking a heap jumps around memory far more than quicksort’s linear scans, so despite matching big-O it tends to be slower in practice. It is the safe fallback, not the speed record.
Insertion sort is not a toy
On small arrays, insertion sort wins. The inner loop is tiny and branch-predictable, and on nearly-ordered input it runs close to O(n) because most elements barely move. That is exactly why the fast sorts stop recursing at small subarrays, usually somewhere between 10 and 32 elements, and finish the job with insertion sort. It lives inside the algorithms you actually run.
def insertion_sort(a):
for i in range(1, len(a)):
cur = a[i]
j = i - 1
while j >= 0 and a[j] > cur:
a[j + 1] = a[j]
j -= 1
a[j + 1] = cur
return aIf the prompt is “the array is nearly sorted, what’s the cheapest thing that works,” insertion sort or Timsort is the answer, not quicksort.
The linear-time sorts and their fine print
Counting sort, radix sort, and bucket sort get past the n log n barrier by using the structure of the keys instead of comparing them. Counting sort tallies how often each value appears and rebuilds the array from the tallies, which is O(n + k) where k is the size of the value range. It’s genuinely linear when k is small, say exam scores from 0 to 100, and a memory disaster when k is large, since sorting 32-bit integers would need a counter array with four billion slots.
Radix sort steps around that by sorting one digit at a time with a stable counting sort per digit, so the range per pass is only the base. That is O(w·n) for w-digit keys, which people quote as linear when the key width is fixed. Bucket sort scatters values into buckets by range, sorts each bucket, and concatenates; it hits O(n + k) on average only when the data spreads evenly. Cluster the input and every value lands in one bucket, dragging the cost back toward whatever sorts that bucket. All three are the right answer only when you can state the assumption they depend on out loud.
What your language actually runs
The sort behind sorted() in Python and Arrays.sort() for objects in Java is Timsort, a hybrid that finds already-ordered runs in the data, pads short runs with insertion sort, and merges the rest. It’s stable and adaptive (near-linear on data that arrives partly ordered), built for the messy arrays real programs hand it rather than random noise. Java sorts primitive arrays with a dual-pivot quicksort instead, on the logic that primitives have no identity, so stability is meaningless and speed is the only thing left to want. C++ std::sort is an introsort: it runs quicksort, watches the recursion depth, and switches to heapsort if quicksort looks headed for its quadratic worst case, cleaning up small pieces with insertion sort at the end. For stability in C++ you call std::stable_sort, which is backed by a merge sort.
Knowing this beats memorizing pseudocode. “Python’s sort is stable, so I can sort by the secondary key first, then by the primary, and the groups stay intact” is the kind of sentence that tells an interviewer you’ve shipped code with these tools rather than only skimmed a reference page.
The follow-ups they reach for
Once you name an algorithm, the interviewer usually pushes on one of a handful of variations. The ones that come up most, phrased close to how they tend to land:
- “Is quicksort stable, and can you make it stable?” You can, by storing original indices as a tiebreaker, at the cost of O(n) space.
- “Sort a billion integers that don’t fit in memory.” External merge sort.
- “You only need the 10 largest of a million values.” A size-10 heap, O(n log k); don’t sort the whole array.
- “The keys are integers from 1 to 1000.” Counting sort, O(n).
- “What does your language’s default sort actually do?” Timsort, dual-pivot quicksort, or introsort, depending on the language and type.
None of these ask you to reproduce code from memory. They reward the person who matches a constraint to the sort that respects it and can say why the obvious default would have been the wrong call.
Drill the patterns next:
