Sorting

Almost no interview problem asks you to implement a sort. Nearly every language ships one, and you should use it.

What problems do ask is whether you notice that sorting is the missing first step — and whether you can say what it costs, what it buys, and what it destroys. That is the whole subject, and it is why this page sits next to the patterns rather than among them: sorting is the enabling move for several of them.

What sorting buys#

An unsorted array supports one thing: looking at every element. Sorting establishes an invariant over the whole array — every element is at least as large as the one before it — and four techniques become available at once:

• Binary search — O(log n) lookup instead of O(n).
• Two pointers from the ends — the converging form needs to know which direction makes a value larger, which is exactly what order provides. 3Sum is unsolvable in O(n²) without the sort in front of it.
• Interval sweeps — one pass suffices only because everything you have not seen yet begins later.
• Adjacency of equals — duplicates end up next to each other, so finding or skipping them becomes a single comparison rather than a set.

The price is O(n log n) and, usually, the original indices. Both matter:

If the answer must be reported in terms of where things were, sorting destroys the thing you were asked for. That is the standard reason Two Sum uses a hash map rather than two pointers.

The workaround, when you need both, is to sort (value, original index) pairs rather than values — worth knowing, and worth saying rather than silently giving up on the sort.

The one to understand: partition#

You will not write a sort, but partition is worth understanding, because it is the shared engine of quicksort and of quickselect — and quickselect does come up, as the O(n) alternative to a heap for “the k-th largest”.

The idea is to pick a pivot and rearrange the array so everything smaller sits before it and everything larger after it. The pivot then holds its final sorted position, and neither side needs to be compared against the other ever again.

Two indices do all the work. The cursor j reads every element once; the boundary i marks the end of the region already known to be below the pivot. The invariant is that everything up to i is smaller and everything between i and j is not — and a value only moves when it is on the wrong side of that line.

function partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1                    // end of the "smaller than pivot" region

    for j = lo .. hi - 1:
        if a[j] < pivot:
            i = i + 1
            swap a[i], a[j]

    swap a[i + 1], a[hi]          // drop the pivot into the gap
    return i + 1                  // its final index

Quicksort recurses into both sides of that split. Quickselect recurses into only the one that contains the index it is looking for — which is why its average cost is O(n) rather than O(n log n): each pass discards roughly half the remaining work instead of processing it. Both are built line by line in the quicksort and quickselect snippets.

The catch is the pivot. Choosing the last element makes an already-sorted array the worst case — every partition peels off one element, and the cost becomes O(n²). Real implementations pick a random pivot or a median-of-three, and mentioning that is usually enough to show you know the failure mode.

Merge sort, and why it still exists#

Quicksort is faster in practice, so merge sort earns its place on two other properties.

It is stable — equal elements keep their original relative order — and its worst case is O(n log n), not O(n²). The cost is O(n) extra space for the merge, which quicksort does not need.

The merge itself is the useful part to have internalised, because it appears far from sorting: two sorted sequences, two cursors, repeatedly take the smaller head. That is the same move as merging two sorted linked lists, and extending it to k sequences is what the heap does. The merge sort snippet walks through it.

Merge sort is also the answer when the data does not fit in memory or has no random access — sorting a linked list, or a file larger than RAM. Quicksort needs to jump around; merge sort only ever reads forward.

Stability, concretely#

Stability matters exactly when you sort more than once, or sort by a key that does not fully determine the order. Sort employees by name, then by department: with a stable sort, the names stay ordered within each department. With an unstable one, they do not, and the first sort was wasted.

Know your language’s default: Python’s sorted and Java’s Collections.sort are stable; C++’s std::sort is not, and std::stable_sort exists for when it matters. This is a reasonable thing to be asked and an easy thing to get wrong.

Sorting without comparisons#

Comparison sorts cannot beat O(n log n) — there are n! possible orderings and each comparison splits the space in two, so log₂(n!) ≈ n log n comparisons are needed. That bound is worth knowing because the way around it is to stop comparing.

Counting sort works when the values come from a small fixed range: tally how many of each, then write them back out in order. O(n + k) for a range of size k.

Sort Colors is that idea at its smallest — three possible values, so a single pass counting them and a second writing them back sorts the array. The Dutch-national-flag solution does it in one pass with three pointers, which is the two-pointer version of the same insight: with only three values, comparisons are not needed at all.

The general signal is a small, known range of values. Ages, letters of the alphabet, grades, colours. If the values are unbounded, you are back to O(n log n).

Comparators#

Most sorting questions in interviews are really comparator questions: the sort is one line and the judgement is in the key.

• Sort by a derived value. K Closest Points to Origin sorts on squared distance — no square root, because it does not change the ordering and costs time and precision.
• Sort by the end rather than the start. Selecting a maximum set of non-overlapping intervals, or Maximum Profit in Job Scheduling, sorts by end time, because finishing earliest leaves the most room for what follows. Merging intervals sorts by start. Same data, opposite key, different problem — intervals covers why.
• Sort a normalised form. Group Anagrams keys on the sorted letters of each word, so every anagram collapses to the same key. Valid Anagram is the same trick with two words and no map.
• Multiple keys. Sort by one field, then break ties with another — most languages take a tuple key directly, and that is cleaner than a hand-written comparator.

A comparator must be consistent: if it says a < b and b < c, it has to say a < c. An inconsistent comparator does not just sort wrongly — in some languages it throws or corrupts memory.

Costs worth having ready#

• Comparison sort lower bound — Ω(n log n). Nothing beats it without exploiting structure.
• Quicksort — O(n log n) average, O(n²) worst, O(log n) stack, not stable, no extra array.
• Merge sort — O(n log n) always, O(n) space, stable, sequential access only.
• Heap sort — O(n log n) always, O(1) space, not stable. Rarely the answer in an interview, but it is what a heap gives you for free.
• Counting sort — O(n + k), needs a bounded range.
• Quickselect — O(n) average, O(n²) worst, for one order statistic rather than all of them.
• Sorting an almost-sorted array — most standard library sorts detect existing runs and approach O(n). Worth mentioning if the problem says the input is nearly ordered.

Recognising it#

Sorting is the missing first step when:

• The brute force compares every pair, and the comparison only depends on the values' order.
• The problem is about intervals, ranges, or scheduling — sort by start or by end, and decide which before writing anything.
• You need to find or skip duplicates, and a hash set is unavailable or wasteful.
• The output itself is required to be in some order — which is easy to miss, and is the last step in Accounts Merge.
• You need the k-th smallest or largest and the whole array is in hand: that is quickselect, not a full sort.

And the check in the other direction: if you need the original positions, or the input arrives as a stream, sorting is not available. Reach for a hash map or a heap instead.

Summary#

Call the library sort; the interview value is in knowing when to call it and what it costs. It buys order, and order is what makes binary search, converging pointers, interval sweeps, and duplicate-adjacency possible — at O(n log n), and at the price of the original indices. Understand partition, because quickselect is a real answer to a real question. Know whether your language’s sort is stable, and know that a small bounded range of values means you can skip comparing altogether.