Sorting Algorithms for Coding Interviews

Microsoft has publicly advised candidates to know at least one O(n log n) sort and preferably two: Merge Sort and Quick Sort. Know these cold — implementation, complexity, and trade-offs. Also understand Insertion Sort for small/nearly-sorted arrays and Counting Sort for bounded integers.

Most of the time you will call the built-in sort and then solve the real problem (often with two pointers or binary search on the sorted data). The skill being tested is recognizing when sorting helps and analyzing the resulting complexity. Memorize the Big O cheat sheet.

Strong candidates discuss stability, in-place vs extra memory, and worst-case behavior unprompted. For example: 'I'll use the built-in sort, which is O(n log n) and stable, then a single linear pass.' That signals maturity. Practice explaining algorithms aloud while watching them in the visualizer.

At bigger technology companies the sorting question is almost never "implement Merge Sort". You will rarely be asked to write a sorting algorithm from scratch, because it tests recall rather than engineering judgement.

What is actually assessed:

• Choosing correctly and justifying it. "Which sort would you use here, and why?" Answering "Quick Sort, because it has the best average-case cache behaviour — though if I needed stability for these records I would use a Merge Sort variant" demonstrates more than any implementation could.
• Recognising when sorting is the hidden first step. This is the highest-value skill on this page. A large share of array and interval problems become straightforward the moment the input is sorted, and interviewers watch for whether you spot it.
• Reasoning about complexity out loud, including the space cost and the worst case, not just the average.
• Knowing what your language's built-in sort actually does — its algorithm, whether it is stable, and its complexity. Not knowing this about a language you claim to know well is a genuine red flag.

The problem patterns where sorting unlocks the solution are worth learning as a set: merging or inserting intervals; the two-pointer family such as two-sum and three-sum on a sorted array; meeting rooms and other scheduling questions; top-k problems (where a heap often beats a full sort); finding anagrams by sorting characters; and detecting duplicates or the largest gap between values. In each case the sort is one line and the insight is recognising that you needed it.

What distinguishes a strong candidate is usually the follow-up, not the answer: mentioning that you would use the standard library rather than hand-rolling, noting the stability requirement before being asked, or observing that a heap gives you the top k in O(n log k) instead of sorting everything in O(n log n).

People waste a great deal of preparation time memorising code they will never be asked to reproduce. The split is fairly clear.

Worth committing to memory — this is a short list, and it is mostly the complexity table:

• Time and space complexity plus stability for the main algorithms. You should be able to state Quick Sort's average and worst case without pausing.
• That comparison-based sorting cannot beat O(n log n), and that Counting and Radix Sort escape it only by not comparing.
• Which algorithm your primary language uses, and whether it is stable.
• The one-line essence of each algorithm: Merge Sort splits and merges; Quick Sort partitions around a pivot; Heap Sort repeatedly extracts the maximum.

Worth understanding instead of memorising: the actual implementations. If you understand that Merge Sort recursively halves until single elements remain and then merges sorted runs, you can rewrite it correctly under pressure without having memorised a single line. Memorised code fails the moment the interviewer changes the problem slightly; understanding does not.

The most efficient way to build that understanding is active rather than passive. Watch an algorithm run step by step in the visualiser and pause to predict the next move before it happens. Then explain it out loud to nobody in particular — if you stumble, you have found the exact gap in your understanding, which re-reading would never have revealed. Then implement it once from that understanding, not from memory. Getting it wrong and debugging it is the point, not a setback.