Sorting & Custom Comparators

Review boundary and corrected contracts

Randomization does not eliminate worst cases and two-way partitioning is quadratic on all-equal values even with random pivots. Quickselect now uses a three-way equal band. Concatenation comparisons cost the string length, so Largest Number is O(n log n·L), not unit-cost comparisons.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the two halves of sorting that design reviews actually probe: partitioning (Dutch national flag, quickselect) and comparator design (when a pairwise rule is more direct than a numeric or tuple key).

Series: LeetCode — From Basics to Production-Ready · Session 53 / 65 · Phase 3 · Advanced & specialised

Watch first

Optional watch-first resources

• Kth Largest Element — NeetCode: watch which partition can be discarded.
• Sort Colors — NeetCode: trace the four-region invariant.
• Quick sort animation — CuriousWalk: follow the in-place swaps; selection continues in only one region.

Why this session exists

Everyone knows how to call sorted(). Nobody gets asked to call sorted(). What design reviews probe is the layer just underneath: can you partition an array in place, can you select the Kth element without paying for a full sort, and can you define an ordering when a pairwise comparison expresses it most directly.

Quickselect is the headline. Finding the Kth largest element with a heap is O(n log k) and is the answer most engineers give. Quickselect gives O(n) average time and is roughly fifteen lines. Producing it unprompted signals that you understand partitioning as a primitive rather than sorting as a black box — and that difference is exactly what a senior loop is listening for.

The comparator half matters for a different reason. In Largest Number, ordinary numeric order and lexicographic order both fail: 3 belongs before 30 because "330" > "303". The direct rule compares a + b with b + a. This does not prove that no independent key exists: the exact rational key derived below induces the same ordering. The practical lesson is to choose a clear correct representation, not to mistake an inconvenient key for an impossible one.

Blank-file warm-up

Five minutes, empty file, no notes. Write both of these from memory:

1. Dutch national flag — partition an array of three values (0, 1, 2) in a single pass, in place, using three pointers.
2. Partition-based select — the quickselect skeleton: pick a pivot, partition, recurse into exactly one side.

If the three-pointer loop comes out wrong, that is today's finding. The DNF loop is the single most commonly mis-remembered short algorithm in the entire design review canon, because the mid pointer advances in two of the three branches and not the third, and that asymmetry does not feel natural.

Pattern anatomy

Both halves of this session share one primitive: partition. You choose a value, sweep the array once, and rearrange so elements land on the correct side of that value. Everything else here is a variation on where the boundaries are and what you do afterwards.

The invariant for Dutch national flag, at every point in the loop, is a four-region split of the array:

• [0, low) — all strictly less than the pivot value
• [low, mid) — all equal to the pivot value
• [mid, high] — unclassified, still to be examined
• (high, n) — all strictly greater than the pivot value

The loop runs while mid <= high, and each iteration shrinks the unclassified region by one. That is the whole proof of termination.

def dutch_flag(nums, pivot=1):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] < pivot:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] > pivot:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1          # do NOT advance mid: the swapped-in value is unseen
        else:
            mid += 1
    return nums

The one line that carries all the difficulty is the high -= 1 branch. When you swap with high, the element that arrives at mid came from the unclassified region and has never been examined. Advancing mid there skips it, and the bug is silent on small inputs.

Quickselect below uses the same three-way partition: values below the pivot, an equal band, then values above it. If k lies inside the equal band, its value is already determined; otherwise continue only on the side containing k. The earlier two-way Lomuto selection was correct on valid indices, but could peel off only one equal value per pass. Grouping equal keys is a performance improvement, not a correction to its returned order statistic.

import random
 
def quickselect(nums, k):
    """Zero-based order statistic; mutates nums. Three-way random partition."""
    import random
    if not 0 <= k < len(nums):
        raise ValueError("k out of range")
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        pivot = nums[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1
        if k < lt:
            hi = lt - 1
        elif k > gt:
            lo = gt + 1
        else:
            return nums[k]
 

Note the loop instead of recursion — the recursion is tail-position, so converting it to a while True costs nothing and removes any stack-depth concern.

And the comparator skeleton, when a pairwise rule is the clearest expression. Both Largest Number implementations assume a nonempty list of non-negative integers:

from functools import cmp_to_key
 
def compare(a, b):
    # return negative if a should come FIRST, positive if b should come first
    if a + b > b + a:
        return -1
    if a + b < b + a:
        return 1
    return 0
 
def largest_number(nums):
    strs = [str(n) for n in nums]
    strs.sort(key=cmp_to_key(compare))
    out = "".join(strs)
    return "0" if out[0] == "0" else out

The cue

You are looking at a sorting-and-selection problem when the statement contains one of these tells:

1. "Kth largest / Kth smallest / median" and the constraints allow mutating the input. That is quickselect. If the input is a stream or must not be mutated, it is a heap instead.
2. "Sort in place with O(1) extra space" and a tiny value domain — three colours, two categories, even/odd. Small domain plus in-place plus one pass equals partition, not a comparison sort.
3. "Arrange / order these so that the resulting X is maximal" where X is a concatenation, a ratio, or a pairing. If you cannot write down a single number per element that produces the ordering, you need a pairwise comparator.
4. "Sort by A, then by B descending, then by C" — use a tuple key when numeric negation expresses the reversed field. For descending strings, stable multi-pass sorting also works: sort the least-significant criterion first, then the more significant ones with their respective reverse flags. A comparator is another option, not a necessity.
5. Counting-style constraints — values bounded by a small constant while n is large. That is counting sort territory: O(n + range) beats O(n log n).

A key computes a sortable value for each element; a comparator supplies pairwise order. A comparator can be convenient even when an exact key exists. Either representation must induce a consistent, transitive order; a rule that cycles among three elements is not repaired by cmp_to_key.

Guided solve

Sort Colors — an array of 0s, 1s and 2s. Sort it in one pass, in place, with constant extra space.

Start with what the naive answers are, because articulating why you are rejecting them is worth real points.

The two-pass counting approach is legitimate: count how many 0s, 1s and 2s there are, then overwrite the array. O(n) time, O(1) space, dead simple, and it works. The reason it is not the intended answer is the "one pass" clause. Say this out loud under a tight review — you show you have a correct baseline before you reach for the clever thing.

The one-pass answer is Dutch national flag with pivot 1. Maintain three pointers as described above. Walk mid forward:

• nums[mid] == 0 → it belongs in the left region. Swap it with nums[low]. If low < mid, the incoming value is from the all-ones region [low, mid); if low == mid, this is a self-swap of the classified 0. Safe to advance both low and mid.
• nums[mid] == 2 → it belongs at the right end. Swap with nums[high], decrement high. The arriving value came from the unclassified region. Do not advance mid.
• nums[mid] == 1 → already in the correct middle region. Advance mid only.

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        v = nums[mid]
        if v == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif v == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1

Trace it once on [2, 0, 1] by hand before you trust it. mid=0 sees a 2, swaps to the end giving [1, 0, 2] with high=1, mid unchanged. mid=0 now sees a 1, advances. mid=1 sees a 0, swaps with low=0 giving [0, 1, 2], both advance. mid=2 > high=1, loop ends. Correct, and the trace takes twenty seconds — do it in the review, it demonstrates the invariant better than any explanation.

Termination: mid increases or high decreases on every iteration, so the gap high - mid strictly shrinks. One pass, O(n) time, O(1) space.

Solo timed

Fifteen minutes each, timer visible, no editorial until the timer fires.

• Kth Largest via quickselect — remember that the Kth largest in a zero-indexed array is the len(nums) - k-th smallest. Get that conversion right before you write the partition.
• Largest Number — the ordering is pairwise, not a key. And there is one edge case that fails every naive submission; think about what the answer should be when the input is all zeros.

If you finish both early, implement Sort an Array (merge sort from scratch, no built-in sort) — it is the cleanest place to practise the merge step you will need again if a linked-list sort shows up.

Common failure modes

Advancing mid after the high swap. The swapped-in value is unclassified, even when it is a 1 rather than a 0. The exact mutant that increments mid after this swap fails on [1, 2, 0]: it exits with [1, 0, 2]. Some short inputs, including [2, 0, 1], still pass and cannot serve as the sole negative control.

Off-by-one in the Kth-largest conversion. k=1 means the largest, which is index n - 1 in sorted order. So the target index is n - k, not n - k - 1 and not k - 1. Write the mapping down before writing the loop.

Random pivots give expected linear selection on suitable partitions, not a worst-case guarantee. A two-way partition still degenerates on equal keys. The revised implementation groups equal keys and skips the whole equal band.

Returning cmp_to_key(compare)(x) semantics backwards. The convention is: negative means a sorts before b. Getting the sign inverted produces a perfectly reversed output and no error, so it looks like a logic bug rather than a convention bug. State the convention aloud as you write the function.

Forgetting that largest_number can produce leading zeros. Input [0, 0] sorts to "00", and the expected answer is "0". One line, always forgotten.

Myth: Finding the Kth largest element requires sorting, so it's O(n log n) at best.

Expected linear time is not a worst-case bound. Three-way partitioning handles duplicate keys; median-of-medians is the separate deterministic selection route.

Steps 1: A comparison sort must distinguish between n! possible orderings, and each comparison yields one bit, so it needs at least log2(n!) ≈ n log n comparisons.

Steps 2: Because that bound is about producing a total order, it does not apply to questions that need less than a total order.

Steps 3: Because 'which element sits at index k' is a single fact rather than a total order, no such lower bound constrains it.

Steps 4: A three-way partition fixes the equal band’s sorted positions in O(n) work. If k is outside that band, only one of the two unequal regions can contain the answer.

Steps 5: With a uniform random pivot, at least a constant fraction of pivot ranks leave at most about three quarters of the active segment on the target side. The expected number of trials before such a shrink is constant. Summing the work across shrinking size scales gives O(n); it is not a promise of exact halves or exactly 2n comparisons.

Compare work counts and then measure on your intended input distribution. Python-level selection can lose to a C-implemented sort despite a better asymptotic bound.

Picture: A pivot is a wall you build across the array. You throw every element to one side of the wall, then look at the wall's position number. If the number you want is left of the wall, you demolish everything right of it and never look at it again.

Trigger: Fires when a problem asks for one position in sorted order rather than the whole sorted array — Kth largest, median, top-K boundary.

Name: Min-heap of size k

Gain: O(n log k) time, O(k) space; works on streams; never mutates the input; trivial to write correctly under pressure

Cost: O(n log(k + 1)) heap work versus expected linear selection; actual elapsed time depends on implementation and data. The heap stores k values.

Name: Quickselect

Gain: O(n) expected time, O(1) extra space, and it signals depth

O(n²) worst case even with randomisation; the expected bound is distinct

Pick: Quickselect when the input is a mutable in-memory array and you are asked for a single Kth element. Heap when the data arrives as a stream, when the input must not be mutated, or when you need the whole top-K set rather than just the boundary element.

Worked variant — Largest Number, comparator and exact key

An exact key does exist. The concatenation comparator remains a useful direct solution.

Arrange a nonempty list of non-negative integers so their concatenation is maximal. Compare adjacent candidates by concatenating them in both directions; correcting an inverted adjacent pair improves the whole concatenation because the surrounding prefix and suffix stay fixed.

from functools import cmp_to_key
 
def largest_number(nums: list[int]) -> str:
    strs = [str(x) for x in nums]
 
    def compare(a: str, b: str) -> int:
        # The pairwise rule: a should come first iff a+b > b+a.
        # cmp contract: negative -> a first, positive -> b first, 0 -> tie.
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0
 
    strs.sort(key=cmp_to_key(compare))
 
    # Edge case: all zeros concatenate to "000...", which must be "0".
    # Checking the FIRST element suffices — it is the largest, so if it
    # is "0" then every element is.
    if strs[0] == "0":
        return "0"
    return "".join(strs)
 
assert largest_number([3, 30, 34, 5, 9]) == "9534330"
assert largest_number([0, 0]) == "0"

An exact key exists. Let A = int(a) and let p be the number of decimal digits in a; similarly define B and q. Comparing the equal-length concatenations is comparing A·10^q + B with B·10^p + A. Rearranging gives A·(10^q − 1) > B·(10^p − 1), equivalently A/(10^p − 1) > B/(10^q − 1). Thus Fraction(int(a), 10**len(a) - 1) is an independent exact key, sorted descending. For 3 and 30, the keys are 3/9 and 30/99. Floating-point approximations can collapse distinct keys, so use exact fractions if choosing this route.

Why the comparator is a valid ordering. Exact rational comparison is transitive, so the concatenation relation is a total preorder: different strings such as "12" and "1212" can tie. Tied strings commute under concatenation. Exchanging any adjacent inverted pair improves the result while preserving everything around it; repeatedly removing inversions leads to a sorted order with a maximal concatenation. This proves both comparator consistency and the greedy objective.

Cost. cmp_to_key creates wrappers whose comparisons call the rule; each concatenation comparison costs O(d) for maximum digit length d. A rational key shifts work to big-integer construction and comparison. Neither representation is universally faster: choose clarity first, then measure for the input scale.

Memory hook — "key if you can, cmp if you must"

The decision procedure, in one line: key if you can, cmp if you must.

• Key — ask whether you can score each element on its own, without looking at any other element, such that sorting by the score gives the answer. Usually yes. Tuples cover multi-level sorts, and for mixed directions on numbers, negate one component: key=lambda p: (p[0], -p[1]).
• Cmp — use a direct pairwise rule when it is simpler to express or explain. Return negative, zero or positive, wrap it in cmp_to_key, and justify transitivity. Pairwise syntax alone does not imply the absence of a key.

For partitioning the peg is "low, mid, high — mid does the walking." In Dutch national flag only mid scans. On a small value swap with low and advance both; on a large value swap with high and retreat only high, because the element you just pulled in from the right end has not been examined yet. Advancing mid there is the single most common bug in the routine.

For quickselect the peg is "partition, then pick a side." Quicksort recurses into both halves; quickselect recurses into one and throws the other away. Discarding one side permits expected linear selection under random pivots; it does not guarantee that every partition halves the work.

What reviewers actually ask

Sorting questions are rarely about sorting. They are about whether you can operate one level below the library call.

• 215 · Kth Largest Element in an Array (Medium) — Practice selection. Probing quickselect. Follow-up: "what is the worst case and how do you avoid it?" — O(n²) remains possible with random pivots; randomisation gives an expected bound, while median-of-medians provides a deterministic linear bound.
• 75 · Sort Colors (Medium) — Practice selection. Probing Dutch national flag. Follow-up: "one pass, constant space" — which rules out counting sort and forces the three-pointer version.
• 179 · Largest Number (Medium) — Practice selection. Probing comparator recognition. Follow-up: "prove your comparator is transitive, allowing ties."
• 937 · Reorder Data in Log Files (Medium) — Practice selection. Probing tuple keys with mixed criteria and stability.
• 56 · Merge Intervals (Medium) — Practice selection. Probing that sorting by start is the enabling move, not the answer.
• 148 · Sort List (Medium) — Practice selection. Probing merge sort on a linked list, where the array-oriented routines do not apply.
• 973 · K Closest Points to Origin (Medium) — Practice selection. Probing the heap-versus-quickselect tradeoff explicitly; both are accepted, and naming both is the strong answer.

The escalation to watch: "can you do better than sorting?" Whenever you have reached for a full sort, be ready to say whether partial ordering suffices — quickselect, a size-K heap, or counting sort when the value range is bounded.

Complexity

Dutch national flag: O(n) time — each iteration either advances mid or retreats high, and they can only meet once. O(1) space, all swaps in place.

Quickselect: O(n) expected time for the three-way random-pivot implementation, by constant-probability shrinkage of the active rank interval. O(n²) worst case remains possible with repeated extreme pivots on distinct values. All-equal values finish after one partition. The iterative code uses O(1) auxiliary space and mutates the array.

Comparator sort: O(n log n) comparisons, each costing O(d) for maximum digit length d, hence O(n·d·log n) time for n at least two under character-operation accounting. Stored decimal strings and the joined output occupy O(n·d), with O(n) sort/wrapper overhead. Treating digit length as bounded recovers O(n) space; it is not O(n) for unbounded strings.

Self-check (answer follows each question).

Q: In the Dutch national flag loop, why do you advance mid after swapping with low but not after swapping with high?

A: When low < mid, [low, mid) contains only pivot-valued elements; when low == mid, the low swap is a self-swap. Both allow mid to advance after the small-value branch. The element at high lies inside the unclassified interval [mid, high], not beyond it, so the high-swap branch must examine its incoming value.

Q: You want the 3rd largest element of a 10-element array using a quickselect written for Kth smallest. What index do you pass?

A: Index 7. The Kth largest is the (n − k)-th smallest in zero-indexed terms: 10 − 3 = 7.

Q: Why use a comparator for largest_number, and is a sort key impossible?

A: The comparator directly tests a+b > b+a. An independent exact key does exist: Fraction(int(a), 10**len(a)-1), sorted descending. The algebra in the worked variant proves equivalence and transitivity; ordinary numeric or lexicographic keys are the ones that fail.

Q: What does random pivot selection guarantee on already-sorted input, and what does it not guarantee?

A: A uniformly random pivot decouples pivot rank from the input order and gives expected linear time with the three-way partition. An unlucky sequence can still be quadratic. Equal values require the equal band to avoid repeated one-value progress.

Q: When should you prefer a size-k min-heap over quickselect?

A: When the data is a stream, when the input must not be mutated, or when you need the entire top-K set rather than just the boundary element.

Q: Median-of-medians gives quickselect a deterministic O(n) worst case. Why is it almost never used in practice?

A: Median-of-medians spends extra work choosing a pivot from five-element groups and recursively selecting their median. That buys deterministic linear worst-case selection; random pivots are simpler and often preferred. Which is faster is an implementation/workload question, not a theorem about all realistic inputs.

Stretch: true

You can now…

• Write quickselect from a blank file and explain why discarding one side gives O(n) average rather than O(n log n).

• Distinguish O(n) expected time with random pivots from the O(n²) worst case and deterministic linear selection.

• Write Dutch national flag with the correct pointer advances — and say why mid does not move after a swap with high.

• Decide between a key and a comparator by asking whether an element can be scored independently.

• Build multi-level tuple keys, including mixed directions via negation on numeric components.

• Derive Largest Number’s concatenation rule and equivalent rational key, and defend their transitivity.

• Answer 'can you do better than sorting?' with quickselect, a size-K heap, or counting sort as appropriate.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Sort Colors goes into the queue at whatever status today's blank-file attempt earned. If the Dutch flag loop came out wrong from memory, it is failed regardless of whether you eventually solved it — the queue tracks retrieval, not eventual success.

• Partition is the primitive; Dutch national flag and quickselect are both just partitioning with different bookkeeping.

• Quickselect answers Kth-largest in O(n) expected time because it discards one whole side after each partition — sorting produces information you did not ask for.

• Randomise the pivot for expected linear selection; retain the quadratic worst-case caveat and the equal-band handling for duplicates.

• A key is a function of one element; a comparator expresses a relation between two. Prefer the clearest consistent ordering, and do not confuse pairwise notation with proof that no key exists.

• The mid pointer advances on the low swap and not the high swap — that asymmetry is the entire difficulty of the DNF loop.

• Kth largest is the (n − k)-th smallest. Write the index conversion down before you write the partition.

Corrective source notes

• Sorting Techniques — Python 3.14 documentation — Python sorting preserves the order of elements that compare equal. Checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.