Sorting & Searching

How it works

Sorting is often the first move rather than the whole answer. Once data is ordered, duplicates are adjacent, pairs can be found with two pointers, intervals line up, and binary search becomes possible. Paying O(n log n) up front frequently turns a quadratic problem into a linear pass.

Interviews still test sorting algorithms directly. Merge sort splits in half, sorts each half and merges, which guarantees O(n log n) and is stable; its merge step also counts inversions. Quicksort partitions around a pivot and is fast in practice but quadratic with bad pivots, which random pivots avoid.

Quickselect reuses the partition step to find the k-th smallest element without sorting everything: after one partition, only one side can contain the answer, so the expected cost is linear.

When values are small integers in a known range, comparison sorts are not the limit. Counting sort and bucket sort place items directly by value in O(n + range). Custom comparators handle the disguised cases, such as ordering numbers to form the largest concatenation.

How to attack it

1. 1Ask whether sorting the input unlocks a simpler pass (two pointers, sweeps, grouping).
2. 2Check whether original positions must be preserved; sort indices or pairs if so.
3. 3Choose the key or comparator, and whether stability matters.
4. 4Use quickselect or a heap if only the k-th element or the top k is needed.
5. 5Use counting or bucket sort when values fall in a small range.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

import random


def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps the sort stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


def quickselect(a, k):
    # k-th smallest (0-based), expected O(n). Mutates a.
    lo, hi = 0, len(a) - 1
    while True:
        p = random.randint(lo, hi)
        a[p], a[hi] = a[hi], a[p]
        store = lo
        for i in range(lo, hi):        # Lomuto partition around a[hi]
            if a[i] < a[hi]:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        if store == k:
            return a[store]
        if store < k:
            lo = store + 1
        else:
            hi = store - 1

What it costs