What they're testing
Whether you know the gap between the textbook algorithm and the shipped one.
The short answer~30 seconds
Most are hybrids: V8 and Python use Timsort (a merge sort that exploits already-sorted runs), while Java's Arrays.sort for primitives uses dual-pivot quicksort. Plain quicksort is avoided because of its O(n²) worst case — on nearly-sorted data or on input an attacker constructed, it degenerates. Introsort handles that by counting recursion depth and switching to heapsort past a threshold.
The long answer
The detail worth raising is STABILITY, because it decides correctness rather than only speed. A stable sort preserves the relative order of equal elements, so sorting by name then by department leaves names ordered within each department. Java uses Timsort (stable) for objects and quicksort (unstable) for primitives — because two equal ints are indistinguishable, so stability is meaningless there.
Timsort wins because real data is rarely random: logs arrive nearly in time order, user lists nearly in id order. It finds existing ascending or descending runs and merges them, so on already-sorted input the cost is O(n) rather than O(n log n). It's an optimisation for the real input distribution, not for the theoretical case.
The most practical point: you should essentially never write a sort. What deserves attention is the COMPARATOR — an inconsistent one (where a < b and b < a are both true) makes Java's Timsort throw IllegalArgumentException, and produces undefined results elsewhere. And in JavaScript, [10, 9, 1].sort() returns [1, 10, 9], because the default comparison is lexicographic.
What they'll ask next
?How do you sort data larger than RAM?
External merge sort: split into memory-sized chunks, sort and spill each, then k-way merge them with a heap. It's exactly what a database does when an ORDER BY doesn't fit work_mem, and it shows up in EXPLAIN as "external merge Disk".
These lose points
- Saying quicksort is "always O(n log n)". On average, yes; worst case it's O(n²), and that worst case can be triggered deliberately.