Which Sorting Algorithm Should I Use?

In production code, use the sort your language already provides — sorted() in Python, Arrays.sort() or List.sort() in Java, std::sort in C++, Array.prototype.sort() with a comparator in JavaScript. These are not lazy defaults. They are hybrids that have been tuned and hardened for decades: Tim Sort detects pre-existing order, Introsort protects against pathological inputs, and both fall back to Insertion Sort on small partitions. Hand-written sorts almost always lose to them, and they lose while also carrying more bugs.

Deliberately choosing an algorithm is worth doing in five situations, and this guide is about those:

• Your keys are bounded integers and you want to beat O(n log n).
• Your data is too large for memory.
• You are on hardware with hard memory or write-cycle limits.
• You need a guarantee (stability, or worst-case time) that the default does not give you.
• You are in an interview, where "use the built-in" is the start of the answer, not the end of it.

Work through these in order and stop at the first one that matches. They are ordered so that the cheapest, most decisive tests come first.

1. Does the data fit in memory? If not, stop here: you want an external merge sort. Nothing else in this list applies until the data fits.
2. Are the keys integers in a small, known range? Grades 0–100, ages, byte values, HTTP status codes. Use Counting Sort for O(n + k) — genuinely linear, and it beats every comparison sort. If the numbers are large but fixed-width (IDs, ZIP codes, phone numbers), use Radix Sort instead.
3. Is the array tiny — say 20 elements or fewer? Use Insertion Sort. The O(n log n) algorithms have setup and recursion overhead that dominates at this size, which is exactly why the standard libraries switch to Insertion Sort for small partitions.
4. Is the data already mostly in order? Append-heavy logs, a table that was sorted before three new rows arrived, timestamps arriving nearly in sequence. Use Tim Sort (or just the built-in, if it is Tim Sort) or Insertion Sort for small cases. Both are adaptive and approach O(n) here, while Quick Sort and Merge Sort do the full amount of work regardless.
5. Do you need stability, or a hard worst-case guarantee? If equal elements must keep their relative order, or an O(n²) worst case is unacceptable, use Merge Sort (or Tim Sort). If you need the worst-case guarantee and O(1) extra memory, Heap Sort is the only common algorithm that provides both.
6. None of the above? Random-ish data, comfortably in memory, just needs to be fast: Quick Sort with a randomised or median-of-three pivot. It is the fastest comparison sort in practice, for reasons that have nothing to do with Big O.

A few data shapes have answers that do not follow from the general path.

Linked lists. Merge Sort, without hesitation. Quick Sort needs random access to partition efficiently and a linked list does not provide it, whereas merging two sorted lists is just pointer rewiring — and it needs no extra array, so Merge Sort is actually O(1) auxiliary space on a list rather than O(n).

You only need the top k, not the full order. Do not sort. Keep a size-k heap and stream the data through it: O(n log k) instead of O(n log n), and it works on data that never fully fits in memory. This is how "top 10 results" is implemented at scale.

You need the median, or the k-th smallest. Again, do not sort. Quickselect uses Quick Sort's partition step but recurses into only one side, giving O(n) average time instead of O(n log n).

Writes are expensive. On EEPROM or flash with limited write endurance, Selection Sort's guaranteed n−1 swaps can beat an algorithm that is asymptotically faster but writes far more often. This is the one situation where an O(n²) algorithm is the professional choice.

Multiple sort keys. Prefer a single comparator over a tuple of keys — sorted(people, key=lambda p: (p.last, p.first)) — rather than sorting twice. Sorting repeatedly with a stable sort also works and is sometimes clearer, but it does more passes over the data.

Say you are sorting one million order records by status, where status is one of eight values, and orders with the same status must stay in the order they were received.

Walk the path. Does it fit in memory? Yes. Are the keys integers in a small range? Yes — eight distinct statuses, so k = 8 against n = 1,000,000. That is Counting Sort's ideal shape, and Counting Sort is stable, which satisfies the second requirement for free.

Comparison sorts would need roughly 20 million comparisons here. Counting Sort makes two passes over the data and one pass over an eight-element tally array. It is not a marginal win; it is an order of magnitude, and it comes purely from noticing that the key space was tiny.

Change one detail — statuses become arbitrary free-text labels — and the answer changes completely. The keys are no longer integers, so Counting Sort is out, stability is still required, so you land on Merge Sort or Tim Sort, i.e. the built-in stable sort. Same data volume, different key type, different algorithm.

Interviewers asking "which sorting algorithm would you use?" are testing whether you ask about the input before answering. The strong response is to ask first: How large is n? Are the keys integers, and bounded? Is the data likely to be partly sorted already? Does equal-element order matter? Are there memory limits? Does it fit in RAM?

Then commit to an answer and justify it in one sentence. "Bounded integer keys and stability required, so Counting Sort — linear time and stable by construction" is a complete answer. So is "unknown distribution, in memory, no stability requirement, so randomised Quick Sort, and I'd mention that std::sort uses Introsort to bound the worst case."

Finally, say what production would do. Noting that you would reach for the built-in in real code, and explaining that it is Tim Sort or Introsort under the hood, signals that you know the difference between an exercise and an engineering decision. More detail in the interview guide.