Sort and Search: The Core Idea

A librarian is handed 50,000 returned books in a heap and asked, "Are any two of these the same edition?" Checking every book against every other is 1.25 billion comparisons. Putting them on the shelf in order first changes the question completely: two copies of the same edition now sit side by side, and one walk along the shelf finds them.

That is how sorting is used in interviews. It is rarely the answer. It is the step that makes the answer easy — order puts near things next to each other. The skill is noticing when that is worth the price, and knowing the tools that go with it: partitioning, selecting one element without sorting everything, defining a custom order, and counting what a merge reveals.

Put numbers on the librarian's trick. Finding the smallest gap between any two of n numbers by comparing every pair is O(n²): at n = 10⁵ that is 5 × 10⁹ comparisons. Sorted, the closest pair must be neighbours, so one pass over adjacent pairs is enough.

1def closest_gap(nums: list[int]) -> int:2    """Smallest difference between any two values (needs at least two)."""3    ordered = sorted(nums)4    return min(b - a for a, b in zip(ordered, ordered[1:]))   # only neighbours matter

On [41, 7, 30, 19, 33] the sorted list is [7, 19, 30, 33, 41], the gaps are 12, 11, 3, 8, and the answer is 3. At n = 10⁵ the sort costs about 1.7 × 10⁶ steps instead of 5 × 10⁹.

How to recognise it

• The problem becomes easy once the input is ordered. Duplicates, closest pairs, grouping, sweeping ranges. Two Pointers and Intervals both open with a sort for this reason.
• You need the k-th element, the median, or the top k. A full sort answers it at O(n log n). Quickselect gets one element into place at O(n) on average.
• A custom order is the question. "Arrange these numbers to form the largest number." Nothing is hard except defining "comes before".
• The values live in a small, known range. Colours 0 to 2, ages 0 to 120, citation counts capped at n. That permits a linear-time counting sort.
• Count pairs i < j with some order condition. "How many pairs are out of order?" The merge step of merge sort sees exactly those pairs.

And the signal that says don't: if the target is O(n), a sort has already broken it. When an interviewer asks "can you beat O(n log n)?", they are asking you to remove the sort — with a hash map, a heap, or a counting sort.

How it works: what a sort buys and what it costs

A sort buys three things. Neighbours: equal or close values become adjacent. Monotone sweeps: a pointer that only moves forward can make decisions, as in two pointers and interval sweeps. Binary search: any question of the form "first element at least x" becomes O(log n).

It costs three things. Time: an O(n log n) floor on the whole solution. Original positions: if the answer needs the input's indices, sort pairs (value, index) or sort a list of indices instead. Space: Python's sorted makes a copy; list.sort sorts in place.

Why can no comparison sort beat O(n log n)? A sort must tell apart all n! possible orderings of its input. Each comparison has two outcomes, so k comparisons can tell apart at most 2ᵏ orderings. You need 2ᵏ ≥ n!, so k ≥ log₂(n!), which is about n log₂ n. That is a limit on information, not on cleverness. The only escape is to stop comparing — to use the values themselves as array positions, which is what counting sort does.

The sorts worth knowing

You will not write a sort at work. You will be asked to explain one, and you need to know what your language actually runs.

Merge sort splits the list in half, sorts each half, and merges the two sorted halves by repeatedly taking the smaller front element. Halving reaches size 1 after log₂ n levels, and each level touches every element once, so it is O(n log n) in every case. It needs O(n) extra space for the merge, and it is stable.

Quicksort picks a pivot, partitions the list so smaller values sit left of it and larger values right, then recurses on both sides. It is in place and very fast in practice, but a pivot that is always the smallest or largest value — say, the last element of an already sorted list — splits n into n − 1 and 0, and the time becomes O(n²). Random pivots make that very unlikely, as long as the values are distinct (see "Where it goes wrong").

What your language runs. Python's list.sort and sorted use Timsort, a stable merge-based hybrid that is O(n log n) in the worst case and close to O(n) on input that is already nearly sorted. Java sorts objects with a stable Timsort but primitives with a dual-pivot quicksort (stability does not matter for primitives). C++ std::sort is an introsort — quicksort that falls back to heapsort — and is not stable; std::stable_sort is. JavaScript's Array.prototype.sort has been required to be stable since 2019. The honest interview answer to "which sort would you use?" is "the built-in one", followed by what it guarantees.

Variants

Each problem lesson in this section is one row of this table.

Two neighbours of this section cover the rest. The size-k heap for the k-th largest and the bucket sort by frequency for the top k are worked in Heaps, including quickselect as a third option. Sort, then sweep is the backbone of Intervals and of the greedy problems.

The templates

Template 1 — merge sort. Know it well enough to modify its merge step, because two problems in this section do exactly that.

1def merge_sort(nums: list[int]) -> list[int]:2    """Return a new sorted list. Stable, O(n log n) in every case."""3    if len(nums) <= 1:4        return nums[:]5    mid = len(nums) // 26    left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])7    merged, i, j = [], 0, 08    while i < len(left) and j < len(right):9        if left[i] <= right[j]:        # <= keeps equal items in input order10            merged.append(left[i])11            i += 112        else:13            merged.append(right[j])14            j += 115    merged.extend(left[i:])            # one side is empty; copy the rest16    merged.extend(right[j:])17    return merged

The <= rather than < is what makes it stable: on a tie, the left item — which came first in the input — goes first. The two extend calls copy whatever is left of the side that did not run out.

Template 2 — three-way partition and quickselect. The partition splits a range into values below, equal to, and above a pivot. Quickselect uses it to find the value that would sit at index k after sorting, and recurses into only one side.

1import random234def partition3(nums: list[int], lo: int, hi: int, pivot: int) -> tuple[int, int]:5    """Three-way partition of nums[lo..hi] around pivot.67    Afterwards nums[lo:lt] < pivot, nums[lt:gt+1] == pivot, nums[gt+1:hi+1] > pivot.8    """9    lt, i, gt = lo, lo, hi10    while i <= gt:11        if nums[i] < pivot:12            nums[lt], nums[i] = nums[i], nums[lt]13            lt += 114            i += 115        elif nums[i] > pivot:16            nums[i], nums[gt] = nums[gt], nums[i]17            gt -= 1                    # the swapped-in value is unseen18        else:19            i += 120    return lt, gt212223def select(nums: list[int], k: int) -> int:24    """Return the value that would sit at index k (0-based) if nums were sorted.2526    Average O(n). Reorders nums in place.27    """28    lo, hi = 0, len(nums) - 129    while True:30        pivot = nums[random.randint(lo, hi)]31        lt, gt = partition3(nums, lo, hi, pivot)32        if k < lt:33            hi = lt - 1                # answer is among the smaller values34        elif k > gt:35            lo = gt + 1                # answer is among the larger values36        else:37            return pivot               # k landed inside the block equal to pivot

Why is quickselect O(n) on average when quicksort is O(n log n)? Quicksort recurses into both halves. Quickselect throws one away. With a good pivot the work is n + n/2 + n/4 + … which adds up to about 2n. The worst case — a bad pivot every time — is still O(n²), and a random pivot makes that very unlikely.

Template 3 — counting sort. When values are integers from 0 to max_value, count them and read the counts back in order.

1def counting_sort(nums: list[int], max_value: int) -> list[int]:2    """Sort integers in 0..max_value without comparing any two of them."""3    counts = [0] * (max_value + 1)4    for x in nums:5        counts[x] += 1                 # the value is the index6    result = []7    for value, times in enumerate(counts):8        result.extend([value] * times)9    return result

It is O(n + k) time and O(k) space, where k is the value range. That is only a win when k is about n or smaller: a million values from 0 to 100 is excellent; a hundred values from 0 to 10⁹ needs a billion counters.

Template 4 — keys, not comparators. Python's sort takes a key function, called once per item.

words.sort(key=len)                                        # by lengthstaff.sort(key=lambda p: (p["dept"], -p["salary"]))        # dept up, salary down

A tuple compares left to right, so the first field decides and later fields break ties. A minus sign flips one numeric field, which reverse=True cannot do because it flips everything. For a text field that must go the other way, use stability: sort by the secondary key first, then by the primary key. The stable second sort keeps the first sort's order inside each group. Only when the order is genuinely pairwise — as in Largest Number — reach for functools.cmp_to_key.

Complexity

Where it goes wrong

1. Assuming a stability you were not given. Two stable passes work in Python, but the same code with C++ std::sort breaks ties at random, and the bug only shows on inputs with equal keys. If unsure, put every key into one tuple and sort once.

2. A comparator that is not consistent. A comparator must be a total order: if a comes before b and b before c, then a comes before c. The classic way to break this is a tolerance — "treat values within 0.001 as equal" — which makes a ≈ b and b ≈ c while a is less than c. The sort's behaviour is then undefined: wrong output or, in some languages, an exception. Never put a tolerance into a comparator; round values into buckets first.

3. Sorting when you only need part of the order. The maximum is one pass, O(n). "Any duplicate?" is a hash set, O(n). The top k is a size-k heap, O(n log k). Before writing sort(), ask what you actually need from the order.

4. A hidden sort inside a loop. key = "".join(sorted(word)) inside a loop over n words adds O(L log L) per word. It is not wrong, but it changes the complexity you claimed. After stating a bound, scan your own code for sort, sorted, in on a list, and nested loops.

5. Two-way partitioning on repeated values. A partition that splits into "less than the pivot" and "the rest" puts every copy of the pivot on one side. On an array of equal values, each round removes a single element, so quicksort and quickselect become O(n²) even with a random pivot, because every pivot is the same value. In a test on 20,000 equal values, a two-way quickselect took about 2.7 seconds; the three-way version above took under a millisecond. Three-way partitioning puts all the copies in the middle block and finishes in one round.