Sorting Algorithms

Every candidate "knows" sorting — right up until an interviewer asks which of the sorts they know is stable, or why their quicksort just went quadratic. Session 2 walks the full taxonomy — bubble, insertion, selection, merge, quick, counting, bucket, radix, heap, topological — but the real syllabus is what sorting teaches: region invariants for two-pointer code, stability as a swap-versus-assign question, recursion shape (merge sort recurses first, quicksort partitions first), and the master theorem that prices any divide-and-conquer. The session then points the recursion lens at Fibonacci, Climbing Stairs, and Pow(x, n) — where one cached variable is the entire difference between O(n) and O(log n).

One Comparator, Nine Algorithms

The session opens with a deceptively small observation: a sorting algorithm never knows what "bigger" means — the order depends entirely on your comparator. Partitioning, merging, swapping are generic machinery; the ordering is injected. That is why LC 179 Largest Number is secretly a sorting question where you only write a comparator: to build the largest number from [3, 30, 34], sort the values as strings by whether a+b > b+a, and let any O(n log n) sort do the rest. When an interviewer hands you "sort by a weird rule," the answer is almost never a new algorithm — it's a comparator.

The roll call for the session: 1) bubble, 2) insertion (plus its shell variant), 3) selection, 4) merge, 5) quick, 6) counting/bucket, 7) radix, 8) heap, 9) topological. The first two go by in one breath: bubble sort compares adjacent pairs and its inner loop shrinks to arr.length - i because the tail is already sorted; insertion sort grows a sorted prefix and sinks each new element leftward into place. Both O(n²), both warm-ups.

Two entries need disambiguation. Heap sort is not "sorting with a heap" — dumping everything into a PriorityQueue and polling it out works, but that's an O(n)-extra-space trick; heap sort proper heapifies the array in place. And topological sort isn't comparison-based ordering at all — it linearizes the dependency edges of a DAG (directed acyclic graph), which is why it lives in the graph sessions rather than here.

Selection Sort: Decide Where the Pointers End First

The idea is one sentence: select the smallest item in the remaining numbers, then swap it into place. What the session actually drills is a discipline it calls "two pointers standing on each other's shoulders" (站肩): before writing a single line of loop, decide where each pointer must be when the loop ends. Here, the outer pointer i can stop at the second-to-last element — once everything before it is settled, a one-element remainder is sorted by definition. The inner pointer j always starts at i + 1 and runs to the end.

public int[] selectionSort(int[] arr) {
    if (arr == null || arr.length <= 1) return arr;
    for (int i = 0; i < arr.length - 1; i++) {   // i stops at the 2nd-to-last — the last one is free
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr, i, minIndex);                  // with minIndex — NOT with the roving j
    }
    return arr;
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Time complexity is O(n²), but say the precise version in an interview: the comparisons count (n−1) + (n−2) + … + 1, an arithmetic series. Space is O(1), and — a detail worth volunteering — selection sort performs at most n−1 swaps, which matters when swaps are expensive. One classic slip to watch for: swapping with the roving j instead of minIndex compiles fine and sorts nothing.

Merge Sort: Recurse First, Sort on the Way Up

Merge sort is the canonical divide-and-conquer: split the big problem into smaller ones and solve them by the same method. The session's framing of recursion is worth quoting: the core of recursion is that "visit" and "do" happen in reverse order. Merge sort recurses all the way down before doing any real work — the sorting happens on the way back up, as the call stack unwinds. Recursion → stack → tree traversal: the recursion tree of merge sort is literally a post-order traversal, and the trace makes it visible. Take 6 4 2 0 | 1 3 5 7: the divide phase splits down to single elements — the base case, where nothing can be divided further — then the conquer phase zips pairs back together: 4 6, 0 2, 1 3, 5 7, then 0 2 4 6 and 1 3 5 7, and finally the fully sorted whole. The conquer step is exactly where the comparator decides priority — which is why LC 179 rides on merge sort's back so naturally.

public class MergeSort {
    private int[] numbers;
    private int[] helper;   // allocated ONCE — not once per merge call

    public void sort(int[] values) {
        this.numbers = values;
        this.helper = new int[values.length];
        mergeSort(0, values.length - 1);
    }

    private void mergeSort(int low, int high) {
        if (low < high) {                        // base case: one element — can't divide anymore
            int middle = low + (high - low) / 2;
            mergeSort(low, middle);              // recurse first…
            mergeSort(middle + 1, high);
            merge(low, middle, high);            // …do the work on the way back up
        }
    }

    private void merge(int low, int middle, int high) {
        for (int i = low; i <= high; i++) helper[i] = numbers[i];
        int i = low, j = middle + 1, k = low;    // j = middle + 1, the classic off-by-one site
        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {        // <= keeps equal elements in order → stable
                numbers[k++] = helper[i++];
            } else {
                numbers[k++] = helper[j++];
            }
        }
        while (i <= middle) numbers[k++] = helper[i++];
        // right-side leftovers are already in their final positions — no copy needed
    }
}

Time: every level of the tree does O(n) merge work and there are log n levels → O(n log n), guaranteed, on any input. Space: the recursion stack is O(log n). The helper looks scarier — log n levels × O(n) each suggests O(n log n) — but the recursion is a DFS: only one root-to-leaf path is alive at any moment, so even if you allocated a new buffer per call, garbage collection keeps the peak at O(n). Best practice is what the code above does anyway: allocate one helper array up front and reuse it.

Two merge details interviewers love to probe: why j = middle + 1 (the right half starts after middle — writing middle double-counts an element), and why the trailing copy loop only handles the left side (any right-side leftovers are already sitting in their final slots).

Quicksort: Partition First, Then Recurse

The session frames quicksort as solving sortK by solving sort2 repeatedly, recursively — and its recursion shape is merge sort's mirror image: sort first, recurse second. Choose a pivot, park it at the last position, then run two pointers toward each other: left starts at the first item, right at the second-to-last. The left pointer hunts for elements that should be on the other side (≥ pivot), the right pointer hunts for elements < pivot; when both are stuck, swap and step. When left passes right, swap the pivot into position left.

The discipline that makes this bug-free is the region invariant. At any time instance: [lo, i) holds elements < pivot (finished), [i, j] is unexplored, and (j, hi−1] holds elements ≥ pivot (finished). Every loop step must preserve those three statements — if you can recite them, you can re-derive the code under pressure.

private Random rand = new Random();

private void quickSort(int[] arr, int lo, int hi) {
    int pivotIndex = lo + rand.nextInt(hi - lo + 1);   // random pivot defends the average case
    int pivot = arr[pivotIndex];
    swap(arr, pivotIndex, hi);                         // park the pivot at the end

    int i = lo, j = hi - 1;
    // invariant: [lo,i) < pivot | [i,j] unexplored | (j,hi-1] >= pivot
    while (i <= j) {
        while (i <= j && arr[i] < pivot) i++;          // left hunts for a big one
        while (i <= j && arr[j] > pivot) j--;          // right hunts for a small one
        if (i <= j) swap(arr, i++, j--);
    }
    swap(arr, i, hi);                                  // pivot lands at its FINAL index

    if (lo < i - 1) quickSort(arr, lo, i - 1);
    if (i + 1 < hi) quickSort(arr, i + 1, hi);
}

The line to remember: after every round, the pivot is exactly where it will be in the final sorted array. That one fact is a whole algorithm in embryo — quick selection: if you only need the k-th element, recurse into just one side and skip the other entirely (it returns in Session 12).

Time: with a good pivot the recurrence is T(n) = 2T(n/2) + O(n) → O(n log n), which is both the best and the average case. With a bad pivot — say, always picking the first element of an already-sorted array — one side is always empty and you pay O(n²). Two defenses: pick the pivot at random (as above), or sample 4–5 candidates and take their median. Space: O(1) auxiliary; counting the recursion stack it's O(log n) in the best case and O(n) in the worst.

Two Partition Regimes — and LC 283

The converging left/right pair is only one way to partition. The other is a same-direction slow/fast pair: [0, slow) holds elements < pivot (finished), [slow, fast) holds elements ≥ pivot (finished), and [fast, …] is unexplored. The fast pointer scans ahead looking for small elements; each time it finds one, it swaps it back to slow and both advance. At the end, swap the pivot into slow. The session compresses the choice into a mnemonic worth keeping: left/right converging → write a while without thinking; slow/fast same-direction → write a for without thinking.

And it names the three questions to answer before writing any pointer code: what does each region mean, what does each pointer mean, and is each boundary open or closed. Most partition bugs are one of these three questions left unanswered.

The scheme adapts to duplicates too: on a 0/1 array like 0 1 1 0 0 1 1 0, the partition condition simply becomes "is it a 0 or a 1" — which is exactly the unordered version of LC 283 Move Zeroes: if you don't care about relative order, just herd every 0 to the right with a converging pair:

public int[] moveZeroes(int[] nums) {
    if (nums == null || nums.length <= 1) return nums;
    int left = 0, right = nums.length - 1;
    // [0,left) non-zero | [left,right] unexplored | (right,n-1] zero
    while (left < right) {
        if (nums[left] != 0) left++;             // if, not a nested while — that flies out of bounds
        else if (nums[right] == 0) right--;
        else swap(nums, left++, right--);
    }
    return nums;
}

The comment is the session's warning verbatim: stepping with a nested while instead of if lets a pointer "fly out" past the other one, because the inner loop no longer re-checks left < right. The if/else chain re-tests the guard on every single step. (The real LC 283 asks you to preserve relative order — that calls for the slow/fast version, which shifts non-zeros forward by assignment and is stable for exactly the reason the next section explains.)

Stability: Swap Breaks It, Assignment Preserves It

Take 5a 5b 2a 2b — two pairs of equal keys, tagged by their original order — and sort by the number. A stable sort must output 2a 2b 5a 5b. Quicksort can't promise that: its long-range swaps teleport an element across the array, happily carrying 2b past 2a. Merge sort never swaps — it assigns elements into the output in encounter order, and its <= comparison always takes the left copy of a tie first. The session's rule of thumb generalizes: swap-based sorts (selection, quick, heap) are unstable; assignment-based sorts (insertion, merge, counting) are stable.

Why anyone cares: multi-key sorting. Sort employees by name, then stable-sort by department — the names stay ordered within each department. And radix sort, coming up next, is built on stable passes; with an unstable inner sort it simply doesn't work.

What the JDK Actually Ships

Java's standard library is a case study in this exact trade-off. For primitive arrays, Arrays.sort uses a tuned quicksort (JDK 6 and earlier) or dual-pivot quicksort (JDK 7+) — both O(n log n), the dual-pivot version typically faster. For Object arrays, it uses a modified merge sort: stable, O(n log n) even in the worst case, and faster when the array is partially sorted. The reasoning is the stability story above: two equal ints are indistinguishable, so stability is meaningless and raw speed wins; two "equal" objects can still be different objects, so re-ordering them is observable behavior. Being able to answer "what does Arrays.sort actually run?" is a cheap way to look senior.

Beating O(n log n): Counting, Bucket, Radix

Comparison-based sorting cannot beat O(n log n). The linear-time sorts get around this by not comparing at all — but the entry fee is that the sequence must have structure, e.g. values confined to a known small range like 1–5.

Counting sort: for 1 3 5 2 2 4 3 5 1 2 with range 1–5, keep an int[5] of counters — count(1)=2, count(2)=3, count(3)=2, count(4)=1, count(5)=2 — then replay the counts in order. One pass to count, one pass to write: O(n) time, O(range) space.

Bucket sort: same idea but each bucket keeps the actual elements (List<List<Integer>>), so it works when values carry payloads or need per-bucket sorting. Still O(n) when the buckets are balanced.

Radix sort: sort multi-digit numbers with one stable pass per digit, least significant digit first. For 123 254 120: the units pass gives 120 123 254, the tens pass keeps 120 123 254, the hundreds pass confirms 120 123 254. O(d·n) for d digits — and note the dependency: each pass must be stable (counting sort is the usual inner engine), otherwise earlier digits' work gets scrambled. This is stability paying rent, one section after we defined it.

Pricing Recursion: The Master Theorem

Both halves of this session — the O(n log n) sorts and the recursion problems that follow — are priced by the same formula. For a recurrence of the form T(n) = a·T(n/b) + O(n^k), compare c = log a / log b against k:

• If c > k — the leaves dominate: T(n) = O(n^c).
• If c < k — the root dominates: T(n) = O(n^k).
• If c = k — every level costs the same: T(n) = O(n^k · log n).

The session's three worked examples: T(n) = 3T(n/3) + O(n) has c = 1 = k → O(n log n). T(n) = 3T(2n/3) + O(1) has c = log 3 / log 1.5 ≈ 2.7 > k → O(n^2.7). T(n) = 4T(n/2) + O(n) has c = 2 > 1 → O(n²). And the one to internalize: T(n) = 2T(n/2) + O(n) — merge sort always, quicksort in the best case — is the c = k = 1 branch, hence O(n log n). When an interviewer asks "why is merge sort n log n?", the master theorem is the one-line answer; the recursion-tree picture (n work per level, log n levels) is the intuition behind it.

Recursion 101: Fibonacci and Climbing Stairs

A recursive function is just a function that calls itself, and the session sorts them into two silhouettes: sol(n) → sol(n−1), sol(n−2) — linear recursion — and sol(n) → sol(n/2) — divide and conquer. The writing recipe is always the same two ingredients: a base case (a null list, a null tree, a trivial true/false) and a recursion rule — f(n) = F(f(n−1)).

LC 70 Climbing Stairs is the cleanest specimen: sol(n) = sol(n−1) + sol(n−2), with sol(0) and sol(1) as base cases. Solved top-down, it is the embryo of recursion; solved bottom-up — start from the base cases and build toward the target — it is the embryo of dynamic programming. The base cases are identical either way; only the direction of travel changes.

The Fibonacci sequence (0 1 1 2 3 5 8 13 21 34 55 89 144…) shows why direction matters. Draw the recursion tree of fib(5): fib(3) appears twice, fib(2) three times — duplicated values everywhere, wasted work unless stored. The level widths run 1, 2, 4, … so the naive version costs O(2ⁿ). Either memoize the top-down version or just go bottom-up:

// naive: T(n) = T(n-1) + T(n-2) → O(2ⁿ) — the tree recomputes fib(3), fib(2), … over and over
public long fibNaive(int n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// bottom-up: the transition only touches i-1 and i-2 → two variables suffice. O(n) time, O(1) space
public long fib(int n) {
    if (n <= 0) return 0;
    long fib1 = 0, fib2 = 1;   // f(i-2), f(i-1)
    for (int i = 2; i <= n; i++) {
        long sum = fib1 + fib2;
        fib1 = fib2;
        fib2 = sum;
    }
    return fib2;
}

The session names the bottom-up worldview precisely: dynamic programming is mathematical induction. The induction rule is the state-transition equation — mem[i] = mem[i−1] + mem[i−2] — and mem[n] is stored as you go. It also hands you the standard optimization move: DP time complexity is usually hard to shrink, so shrink space instead — read the transition equation, see which states it actually touches (here: only i−1 and i−2), and drop the dimension: O(n) space becomes O(1), array becomes two variables. That move — 降维, dimension reduction — is a recurring trick in the DP sessions.

LC 50 Pow(x, n): One Cached Variable, Two Complexity Classes

Implement myPow(x, n). Solution 1 multiplies x together n times — O(n), fine, boring. Solution 2 looks like divide and conquer: myPow(x, n/2) * myPow(x, n − n/2), splitting n in half (the n − n/2 handles odd n). Here's the interview trap: it's still O(n). Two uncached recursive calls mean the node count doubles at every level — 1, 2, 4, …, 2^(log n) ≈ n nodes of O(1) work. Splitting the problem bought nothing, because both halves compute the same value independently.

Solution 3 changes one line: compute the half once, store it in a variable, square it. The tree collapses into a chain of log n frames:

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) {
        if (n == Integer.MIN_VALUE) {   // -n would overflow int — peel one factor first
            n++;
            n = -n;
            x = 1 / x;
            return x * myPow(x, n);    // the extra x covers the peeled exponent
        }
        n = -n;
        x = 1 / x;
    }
    double tmp = myPow(x, n / 2);      // cache the half — THE optimization
    return (n % 2 == 0) ? tmp * tmp : x * tmp * tmp;
}

The negative-exponent handling is where candidates get filtered. The natural move — n = −n; x = 1/x — has a lurking overflow: Integer.MIN_VALUE is −2,147,483,648, and negating it doesn't fit in an int. The fix: increment n once (peel a single factor of 1/x off), negate the now-safe value, and multiply that peeled factor back in front of the recursive call. This is precisely the caching lesson and the corner-case lesson from the sorting half of the session, compressed into ten lines.

Problem Checklist