Randomized Quicksort / Quickselect

Why Randomized Quicksort / Quickselect Matters

Suppose a dashboard receives eight response times: $[7,2,9,2,5,1,8,2]$. To display every value in increasing order, it needs a sorting algorithm. To find only the sixth-smallest value, it needs an order statistic: the answer is $7$, and sorting all the other values is unnecessary.

Quicksort and Quickselect share a powerful operation: choose a pivot and partition the data into values smaller than, equal to, and larger than that pivot. Quicksort continues on both unequal regions to order the whole array. Quickselect continues on at most one region, the one containing the requested rank. Random pivot choices avoid tying performance to an unfortunate fixed pivot rule such as always choosing the first value.

You will implement both algorithms using the same in-place three-way partition, trace every comparison and swap in a small run, and verify matching outputs in Python, C++, and Java. The three-way split is especially useful when many values repeat: once the equal block is identified, neither algorithm needs to process that block again.

Core Concepts and Terminology

The input is an array $A$ of comparable values. The runnable examples use signed $32$-bit integers, so equality and ordering are exact. Quicksort mutates $A$ into a nondecreasing permutation of the original values. Quickselect also mutates $A$ and returns the value that would occupy zero-based position $k$ in a sorted copy, requiring $0\le k\lt n$. Repeated values occupy repeated ranks; the rank is not a rank among distinct values.

Every active range is half-open: $[\mathrm{lo},\mathrm{hi})$ includes lo and excludes hi, with length $m=\mathrm{hi}-\mathrm{lo}$. Choose a pivot index in this range and copy its value into a separate variable $p$. The pivot's original array slot may move during partitioning; keeping the copied value avoids changing the comparison target accidentally.

A completed partition returns boundaries $\mathrm{lt}$ and $\mathrm{gt}$ such that

$$A[\mathrm{lo}:\mathrm{lt}]\lt p,\qquad A[\mathrm{lt}:\mathrm{gt}]=p,\qquad A[\mathrm{gt}:\mathrm{hi}]\gt p.$$

These expressions mean that every value in the corresponding slice has the stated relationship to $p$. They do not mean the unequal slices are internally sorted. Because $p$ was copied from the active range, the equal slice is nonempty, which guarantees progress.

For the sample, a uniform index selects pivot value $2$ with probability $3/8$, since it occupies three positions. Each of $1,5,7,8,9$ has probability $1/8$. Choosing uniformly among the six distinct values would be a different distribution. A balanced split is helpful, but randomization does not promise that every pivot is balanced.

How Randomized Quicksort / Quickselect Works, Step by Step

Use the Dutch national flag partition with four regions. Initially set $\mathrm{lt}=i=\mathrm{lo}$ and $\mathrm{gt}=\mathrm{hi}$. Before every iteration:

• $[\mathrm{lo},\mathrm{lt})$ contains values smaller than $p$.
• $[\mathrm{lt},i)$ contains values equal to $p$.
• $[i,\mathrm{gt})$ is unclassified.
• $[\mathrm{gt},\mathrm{hi})$ contains values larger than $p$.

While $i\lt\mathrm{gt}$, classify $A[i]$. If it is smaller than $p$, swap it with $A[\mathrm{lt}]$, then advance both $\mathrm{lt}$ and $i$. If it is larger, decrement $\mathrm{gt}$ and swap $A[i]$ with $A[\mathrm{gt}]$; leave $i$ unchanged because the incoming value has not been classified. If it equals $p$, advance only $i$.

Each iteration reduces the unclassified length $\mathrm{gt}-i$ by exactly one. Consequently, partitioning a range of length $m$ performs exactly $m$ classification iterations, even when some iterations revisit the same array index. Swaps preserve the multiset of values.

flowchart TD
    A["Active range with at least two values"] --> B["Choose pivot; set lt = i = lo, gt = hi"]
    B --> C{"i less than gt?"}
    C -->|Yes| D{"Compare A[i] with pivot"}
    D -->|Smaller| E["Swap with lt; advance lt and i"]
    D -->|Equal| F["Advance i"]
    D -->|Larger| G["Decrease gt; swap with i; keep i"]
    E --> C
    F --> C
    G --> C
    C -->|No| H{"Requested task?"}
    H -->|Sort| I["Sort both unequal ranges"]
    H -->|Select| J{"Position of k?"}
    J -->|Before lt| K["Continue in left range"]
    J -->|In equal range| L["Return A[k]"]
    J -->|At or after gt| M["Continue in right range"]

For Quicksort, stop on ranges of length zero or one. After partitioning, sort the two unequal ranges and leave the equal range untouched. The implementation recurses only into the smaller unequal range and uses a loop to process the larger one. This changes the call-stack usage, not the sorting result. On equal-size sides, it recurses into the right side first; specifying that tie rule also makes the random draw order reproducible.

For Quickselect, maintain $\mathrm{lo}\le k\lt\mathrm{hi}$, with $k$ remaining an absolute array index throughout. If $k\lt\mathrm{lt}$, replace hi by lt. If $k\ge\mathrm{gt}$, replace lo by gt. Otherwise return $A[k]$: it lies in the equal block and has the requested value. A singleton active range supplies the answer directly, without another partition. Do not subtract the discarded prefix from $k$ in this absolute-index version.

Worked Example with a Full Trace

Use $A=[7,2,9,2,5,1,8,2]$, zero-based target rank $k=5$, and seed $6$. The code's specified generator first picks index $1$, so copy pivot $p=2$. Start with $(\mathrm{lt},i,\mathrm{gt})=(0,0,8)$.

The following table records the state after every classification. A “swap” names zero-based indices, and a self-swap is omitted by the code. The comparisons column counts only evaluated key comparisons: < costs one, while reaching > costs one additional comparison.

The first partition therefore has $8$ scans, $15$ key comparisons, and $4$ nontrivial swaps. Its equal block is $[1,4)$. Quicksort leaves that block and the singleton $[0,1)$ alone, then processes $[4,8)$. Quickselect also keeps $[4,8)$ because $k=5\ge4$.

The next table finishes the run. The initial state before the first row is the original array; every listed pivot index refers to the array as it exists immediately before that partition. Generator states are recorded after the accepted draw. None of these draws is rejected.

Within partition $2$, the examined values are $5,8,9,7$. The first two advance i; $9$ swaps with index $7$, bringing $7$ into the scan position; $7$ then swaps with the equal-region boundary. The resulting left range is $[4,6)$ and the right range is the singleton $[7,8)$. Within partition $3$, $5$ is smaller than $7$ and requires only an omitted self-swap, then $7$ extends the equal block. No further work remains for Quicksort.

Quickselect keeps $[4,6)$ after partition $2$ because $5\lt6$, then stops in partition $3$ because $5\in[5,6)$. Both runs happen to use the same three partitions here. Their totals are $14$ scans, $24$ key comparisons, $6$ nontrivial swaps, and $3$ raw generator draws.

The selected array happens to be completely sorted in this example. That is incidental: Quickselect promises only the selected value and its partition postcondition. For example, with target rank $2$ on a fresh copy, it stops after the very first partition with $[1,2,2,2,5,8,9,7]$; the suffix remains unsorted.

Implementation in Python, C++, and Java

Each panel is a standalone program implementing both algorithms with the same range convention, branch order, side-order tie rule, and sample. Both mutate their input arrays; the sample creates two copies so that selecting does not start from the sorting run's rearranged data. Quicksort accepts an empty array, while selecting from one rejects the rank. The supported seed range is $1$ through $2147483646$, and array length must not exceed $2147483646$.

Using the same numeric seed with three unrelated language-library generators would not generally reproduce the same pivot sequence. Instead, all three programs specify the same small educational generator:

$$s\leftarrow(16807s)\bmod2147483647,\qquad r=s-1.$$

The raw values $r$ lie in $[0,B)$ with $B=2147483646$. To sample an offset below $m$, calculate $L=B-(B\bmod m)$, discard draws with $r\ge L$, and return $r\bmod m$ otherwise. The accepted interval has a multiple of $m$ values, with equal counts for each residue. Thus this conversion avoids modulo bias if the raw draws are uniform; it does not turn a deterministic generator into independent randomness. Use $64$-bit arithmetic for the state multiplication in C++ and Java so that it cannot overflow.

The generator is chosen for transparent, portable replay, not for cryptographic security or as a proof of the ideal-random expected-time theorem. For a fixed seed, every pivot is deterministic. The theoretical analysis below assumes fresh independent uniform pivot indices, and the rejection sampler has expected fewer than two raw draws per offset under independent uniform raw draws. The implementations report the actual draw count, including rejected draws.

Statistics have precise meanings: partitions counts completed partition calls, scans counts classification iterations, comparisons counts evaluated < and > tests against the copied pivot, swaps counts swaps of two different positions, and draws counts state updates in the generator. Loop tests, rank comparisons, seed checks, and integer arithmetic are not key comparisons. A swap of equal-valued entries still counts if their indices differ.

class RNG:
    MOD = 2147483647
    RANGE = MOD - 1

    def __init__(self, seed):
        if not isinstance(seed, int) or not 1 <= seed < self.MOD:
            raise ValueError("seed must be in 1..2147483646")
        self.state = seed
        self.draws = 0

    def below(self, bound):
        if not 1 <= bound <= self.RANGE:
            raise ValueError("invalid random bound")
        limit = self.RANGE - self.RANGE % bound
        while True:
            self.state = (16807 * self.state) % self.MOD
            self.draws += 1
            r = self.state - 1
            if r < limit:
                return r % bound


class Stats:
    def __init__(self):
        self.partitions = self.scans = self.comparisons = self.swaps = self.draws = 0


def swap(a, i, j, stats):
    if i != j:
        a[i], a[j] = a[j], a[i]
        stats.swaps += 1


def partition3(a, lo, hi, rng, stats):
    pivot = a[lo + rng.below(hi - lo)]
    lt, i, gt = lo, lo, hi
    stats.partitions += 1
    while i < gt:
        stats.scans += 1
        stats.comparisons += 1
        if a[i] < pivot:
            swap(a, lt, i, stats)
            lt += 1
            i += 1
        else:
            stats.comparisons += 1
            if a[i] > pivot:
                gt -= 1
                swap(a, i, gt, stats)
            else:
                i += 1
    return lt, gt


def check_length(a):
    if len(a) > RNG.RANGE:
        raise ValueError("array exceeds generator range")


def quicksort(a, seed=6):
    check_length(a)
    rng, stats = RNG(seed), Stats()

    def sort_range(lo, hi):
        while hi - lo > 1:
            lt, gt = partition3(a, lo, hi, rng, stats)
            if lt - lo < hi - gt:
                sort_range(lo, lt)
                lo = gt
            else:
                sort_range(gt, hi)
                hi = lt

    sort_range(0, len(a))
    stats.draws = rng.draws
    return stats


def quickselect(a, k, seed=6):
    check_length(a)
    if not isinstance(k, int) or not 0 <= k < len(a):
        raise ValueError("k must be a valid zero-based rank")
    rng, stats = RNG(seed), Stats()
    lo, hi = 0, len(a)
    while hi - lo > 1:
        lt, gt = partition3(a, lo, hi, rng, stats)
        if k < lt:
            hi = lt
        elif k >= gt:
            lo = gt
        else:
            stats.draws = rng.draws
            return a[k], stats
    stats.draws = rng.draws
    return a[lo], stats


def main():
    original = [7, 2, 9, 2, 5, 1, 8, 2]
    ordered = original.copy()
    s = quicksort(ordered)
    selected = original.copy()
    value, t = quickselect(selected, 5)
    print("sorted = [" + ", ".join(map(str, ordered)) + "]")
    print(f"sort: partitions={s.partitions}, scans={s.scans}, comparisons={s.comparisons}, swaps={s.swaps}, draws={s.draws}")
    print(f"rank 5 = {value}")
    print("selected = [" + ", ".join(map(str, selected)) + "]")
    print(f"select: partitions={t.partitions}, scans={t.scans}, comparisons={t.comparisons}, swaps={t.swaps}, draws={t.draws}")
    sort_ok = ordered == [1, 2, 2, 2, 5, 7, 8, 9]
    select_ok = (value == 7 and selected[5] == value
                 and all(x <= value for x in selected[:5])
                 and all(x >= value for x in selected[6:]))
    print("checks = " + ("PASS" if sort_ok and select_ok else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>
using Array = std::vector<int>;

struct RNG {
    static constexpr std::int64_t MOD = 2147483647;
    static constexpr std::int64_t RANGE = MOD - 1;
    std::int64_t state, draws = 0;
    explicit RNG(std::int64_t seed) : state(seed) {
        if (seed < 1 || seed >= MOD) throw std::invalid_argument("invalid seed");
    }
    int below(int bound) {
        if (bound < 1 || bound > RANGE) throw std::invalid_argument("invalid random bound");
        std::int64_t limit = RANGE - RANGE % bound;
        for (;;) {
            state = (16807 * state) % MOD;
            ++draws;
            std::int64_t r = state - 1;
            if (r < limit) return static_cast<int>(r % bound);
        }
    }
};
struct Stats {
    std::int64_t partitions = 0, scans = 0, comparisons = 0, swaps = 0, draws = 0;
};
void swap_items(Array& a, int i, int j, Stats& s) {
    if (i != j) { std::swap(a[i], a[j]); ++s.swaps; }
}
std::pair<int, int> partition3(Array& a, int lo, int hi, RNG& rng, Stats& s) {
    int pivot = a[lo + rng.below(hi - lo)];
    int lt = lo, i = lo, gt = hi;
    ++s.partitions;
    while (i < gt) {
        ++s.scans; ++s.comparisons;
        if (a[i] < pivot) {
            swap_items(a, lt, i, s); ++lt; ++i;
        } else {
            ++s.comparisons;
            if (a[i] > pivot) { --gt; swap_items(a, i, gt, s); }
            else ++i;
        }
    }
    return {lt, gt};
}
void check_length(const Array& a) {
    if (a.size() > static_cast<std::size_t>(RNG::RANGE)) throw std::invalid_argument("array too large");
}
void sort_range(Array& a, int lo, int hi, RNG& rng, Stats& s) {
    while (hi - lo > 1) {
        auto bounds = partition3(a, lo, hi, rng, s);
        int lt = bounds.first, gt = bounds.second;
        if (lt - lo < hi - gt) {
            sort_range(a, lo, lt, rng, s); lo = gt;
        } else {
            sort_range(a, gt, hi, rng, s); hi = lt;
        }
    }
}
Stats quicksort(Array& a, std::int64_t seed = 6) {
    check_length(a); RNG rng(seed); Stats s;
    sort_range(a, 0, static_cast<int>(a.size()), rng, s);
    s.draws = rng.draws; return s;
}
std::pair<int, Stats> quickselect(Array& a, int k, std::int64_t seed = 6) {
    check_length(a);
    if (k < 0 || static_cast<std::size_t>(k) >= a.size()) throw std::invalid_argument("invalid rank");
    RNG rng(seed); Stats s; int lo = 0, hi = static_cast<int>(a.size());
    while (hi - lo > 1) {
        auto bounds = partition3(a, lo, hi, rng, s);
        int lt = bounds.first, gt = bounds.second;
        if (k < lt) hi = lt;
        else if (k >= gt) lo = gt;
        else { s.draws = rng.draws; return {a[k], s}; }
    }
    s.draws = rng.draws; return {a[lo], s};
}
void print_array(const Array& a) {
    std::cout << '[';
    for (std::size_t i = 0; i < a.size(); ++i) { if (i) std::cout << ", "; std::cout << a[i]; }
    std::cout << "]\n";
}
void print_stats(const char* label, const Stats& s) {
    std::cout << label << ": partitions=" << s.partitions << ", scans=" << s.scans
              << ", comparisons=" << s.comparisons << ", swaps=" << s.swaps << ", draws=" << s.draws << '\n';
}
int main() {
    Array original = {7, 2, 9, 2, 5, 1, 8, 2}, ordered = original;
    Stats s = quicksort(ordered); Array selected = original;
    auto result = quickselect(selected, 5); int value = result.first;
    std::cout << "sorted = "; print_array(ordered); print_stats("sort", s);
    std::cout << "rank 5 = " << value << '\n';
    std::cout << "selected = "; print_array(selected); print_stats("select", result.second);
    Array expected = {1, 2, 2, 2, 5, 7, 8, 9};
    bool ok = ordered == expected && value == 7 && selected[5] == value;
    for (int i = 0; i < 5; ++i) ok = ok && selected[i] <= value;
    for (int i = 6; i < 8; ++i) ok = ok && selected[i] >= value;
    std::cout << "checks = " << (ok ? "PASS" : "FAIL") << '\n';
    return 0;
}

import java.util.Arrays;

public class Main {
    static class RNG {
        static final long MOD = 2147483647L, RANGE = MOD - 1;
        long state, draws;
        RNG(long seed) {
            if (seed < 1 || seed >= MOD) throw new IllegalArgumentException("invalid seed");
            state = seed;
        }
        int below(int bound) {
            if (bound < 1 || bound > RANGE) throw new IllegalArgumentException("invalid random bound");
            long limit = RANGE - RANGE % bound;
            while (true) {
                state = (16807L * state) % MOD; ++draws;
                long r = state - 1;
                if (r < limit) return (int)(r % bound);
            }
        }
    }
    static class Stats { long partitions, scans, comparisons, swaps, draws; }
    static class Selection {
        final int value; final Stats stats;
        Selection(int value, Stats stats) { this.value = value; this.stats = stats; }
    }
    static void swap(int[] a, int i, int j, Stats s) {
        if (i != j) { int t = a[i]; a[i] = a[j]; a[j] = t; ++s.swaps; }
    }
    static int[] partition3(int[] a, int lo, int hi, RNG rng, Stats s) {
        int pivot = a[lo + rng.below(hi - lo)];
        int lt = lo, i = lo, gt = hi; ++s.partitions;
        while (i < gt) {
            ++s.scans; ++s.comparisons;
            if (a[i] < pivot) { swap(a, lt, i, s); ++lt; ++i; }
            else {
                ++s.comparisons;
                if (a[i] > pivot) { --gt; swap(a, i, gt, s); }
                else ++i;
            }
        }
        return new int[] {lt, gt};
    }
    static void checkLength(int[] a) {
        if (a.length > RNG.RANGE) throw new IllegalArgumentException("array too large");
    }
    static void sortRange(int[] a, int lo, int hi, RNG rng, Stats s) {
        while (hi - lo > 1) {
            int[] bounds = partition3(a, lo, hi, rng, s); int lt = bounds[0], gt = bounds[1];
            if (lt - lo < hi - gt) { sortRange(a, lo, lt, rng, s); lo = gt; }
            else { sortRange(a, gt, hi, rng, s); hi = lt; }
        }
    }
    static Stats quicksort(int[] a, long seed) {
        checkLength(a); RNG rng = new RNG(seed); Stats s = new Stats();
        sortRange(a, 0, a.length, rng, s); s.draws = rng.draws; return s;
    }
    static Selection quickselect(int[] a, int k, long seed) {
        checkLength(a);
        if (k < 0 || k >= a.length) throw new IllegalArgumentException("invalid rank");
        RNG rng = new RNG(seed); Stats s = new Stats(); int lo = 0, hi = a.length;
        while (hi - lo > 1) {
            int[] bounds = partition3(a, lo, hi, rng, s); int lt = bounds[0], gt = bounds[1];
            if (k < lt) hi = lt;
            else if (k >= gt) lo = gt;
            else { s.draws = rng.draws; return new Selection(a[k], s); }
        }
        s.draws = rng.draws; return new Selection(a[lo], s);
    }
    static void printStats(String label, Stats s) {
        System.out.println(label + ": partitions=" + s.partitions + ", scans=" + s.scans
            + ", comparisons=" + s.comparisons + ", swaps=" + s.swaps + ", draws=" + s.draws);
    }
    public static void main(String[] args) {
        int[] original = {7, 2, 9, 2, 5, 1, 8, 2}, ordered = original.clone();
        Stats s = quicksort(ordered, 6); int[] selected = original.clone();
        Selection result = quickselect(selected, 5, 6); int value = result.value;
        System.out.println("sorted = " + Arrays.toString(ordered)); printStats("sort", s);
        System.out.println("rank 5 = " + value);
        System.out.println("selected = " + Arrays.toString(selected)); printStats("select", result.stats);
        int[] expected = {1, 2, 2, 2, 5, 7, 8, 9};
        boolean ok = Arrays.equals(ordered, expected) && value == 7 && selected[5] == value;
        for (int i = 0; i < 5; ++i) ok = ok && selected[i] <= value;
        for (int i = 6; i < 8; ++i) ok = ok && selected[i] >= value;
        System.out.println("checks = " + (ok ? "PASS" : "FAIL"));
    }
}

Use Python 3, C++14 or later, or Java 17 or later. Run Python directly; compile C++ with g++ -std=c++14 -O2 main.cpp -o quick; compile and run Java with javac Main.java and java Main. Every program prints these six lines:

• sorted = [1, 2, 2, 2, 5, 7, 8, 9]
• sort: partitions=3, scans=14, comparisons=24, swaps=6, draws=3
• rank 5 = 7
• selected = [1, 2, 2, 2, 5, 7, 8, 9]
• select: partitions=3, scans=14, comparisons=24, swaps=6, draws=3
• checks = PASS

The example's check verifies the expected full sort, selected value, and selection inequalities. A stronger general test must also verify preservation of the multiset, since a faulty algorithm could return the right rank value while corrupting other entries. Replaying a seed validates a particular path; testing many seeds and small exhaustive inputs exercises many other paths.

Complexity, Correctness, and Invariants

Partitioning a nonempty active range of length $m$ performs exactly $m$ scans and between $m$ and $2m$ key comparisons in this implementation, with $O(1)$ extra state. Pivot selection overhead is accounted for separately through the generator draws. The following bounds use constant-cost key comparisons and the usual ideal uniform-pivot model for expected running time.

Quicksort's best case over all allowed arrays is $\Theta(n)$: on an all-equal array of length at least two, one partition ends the entire sort. For distinct keys, balanced splits instead give best-case $\Theta(n\log n)$ work. For every fixed input its expected work is $O(n\log n)$, and on distinct-key inputs it is $\Theta(n\log n)$. Its worst-case partition work is $\Theta(n^2)$: repeated extreme pivots can leave active sizes $n,n-1,\ldots,2$. Duplicates can reduce the work substantially.

Quickselect's best and expected work are $\Theta(n)$ for nontrivial input; even a first pivot that answers the query requires a full initial partition. Its worst-case work is $\Theta(n^2)$ if pivots repeatedly discard only one value while the requested rank stays in the long side. Empty and singleton sort calls, and singleton selection, take constant time.

The implemented Quicksort has an $O(\log n)$ upper bound on live auxiliary stack space for every pivot sequence: the recursively chosen smaller side has size at most $(m-1)/2$. The larger side reuses the current frame through a loop. Some inputs, including all-equal arrays and repeated extreme splits, use only constant stack space despite very different running times. Quickselect is iterative and uses $O(1)$ live auxiliary space. Caller-made copies and printed output are excluded; the sample's copies use $\Theta(n)$ additional storage. Java also allocates small boundary objects during execution, so total allocation over time differs from live auxiliary space.

Why does randomization help? For distinct keys, let $Q(m)$ be expected total partition scans for sorting $m$ items. Since every pivot rank $r$ from $0$ through $m-1$ is equally likely,

$$Q(m)=m+\frac{1}{m}\sum_{r=0}^{m-1}\bigl(Q(r)+Q(m-1-r)\bigr),\qquad m\ge2,$$

with $Q(0)=Q(1)=0$. This recurrence grows as $\Theta(m\log m)$. The familiar exact comparison formulas for other Quicksort partition schemes should not be substituted for these measured counters: this partition scans the pivot too, and sometimes performs two relational tests per scan.

For Quickselect, call a pivot good when its rank is in the middle half of the active elements, up to harmless integer rounding. A uniformly sampled index has at least a constant probability of being good, and a good pivot leaves at most about $3m/4$ elements in either unequal side. Duplicates only help this removal argument by making an entire equal block available to discard or answer the query. The expected number of trials before a good pivot is constant, while bad pivots never increase the active size. Grouping work into shrinking-size phases gives

$$\mathbb E[T(n)]\le Cn\left(1+\frac34+\left(\frac34\right)^2+\cdots\right)=O(n),$$

for a suitable constant $C$ that absorbs partition cost, the expected trials per phase, and small-range rounding. The initial scan gives the matching $\Omega(n)$ lower bound. This expectation is over pivot choices on a fixed input, not an assumption that real-world input arrays arrive in random order.

A proof by cases establishes the invariant. In the smaller branch, the swapped-out value from the equal region is equal to $p$, so increasing both boundaries restores the regions; if that region was empty, the operation is simply a self-swap. In the larger branch, the outgoing value enters the larger region while the incoming value remains unclassified. In the equal branch, advancing $i$ extends the equal region. Initially the classified regions are empty; when $i=\mathrm{gt}$, no unclassified values remain.

For sorting correctness, apply induction on active-range length: each recursive or iterated child is strictly smaller, each child becomes sorted, and all left values are smaller than the equal block, which is smaller than all right values. For selection, partitioning identifies exactly which absolute positions the equal values occupy in a sorted arrangement of the active multiset. The discarded left and right regions stay on the correct sides of every remaining candidate, so when $k$ reaches an equal block or singleton, the returned value has the original requested rank.

Variants, Pitfalls, and Optimizations

The most expensive duplicate-key mistake is repeatedly processing values already known to equal the pivot. A two-way scheme that puts every equal key on one side can leave sizes $n-1$ and $0$ on an all-equal input, even if the pivot index is randomized. Randomization changes which identical element is selected; it cannot create a useful split between equal values. Three-way partitioning removes the whole equal block in one pass.

Other practical choices affect different properties:

• Keep endpoint conventions consistent. This partition returns an equal interval $[\mathrm{lt},\mathrm{gt})$, not a single final pivot slot. Its children are $[\mathrm{lo},\mathrm{lt})$ and $[\mathrm{gt},\mathrm{hi})$. Lomuto and Hoare partitions have different return contracts; their recursion rules are not interchangeable with these.
• Reclassify incoming values. Never advance $i$ immediately after the greater-than swap. The trace shows why the same index may need several visits, even though the total number of scans is exactly the original range length.
• Keep the pivot value fixed. A reference to the original pivot slot may start referring to another key after swaps. Copy the integer pivot or use a design that otherwise protects the key being compared.
• Preserve the rank convention. Zero-based rank $k$ is the $(k+1)$-st smallest value. Absolute-index selection keeps $k$ unchanged; a version that copies or rebases subarrays must adjust its local rank explicitly. For an even-length median, specify whether you want the lower middle, upper middle, or mean of the two; selecting one rank does not compute that mean.
• Improve worst-case guarantees deliberately. Introsort falls back to heapsort when partition depth becomes too large, giving worst-case $O(n\log n)$ sorting. For selection, a fallback policy must account for the work already spent: a depth threshold alone can permit $O(n\log n)$ earlier work, so it is not by itself a proof of worst-case linear selection. A linear work budget followed by a correct deterministic linear selector can support such a guarantee.
• Use small-range cutoffs or better pivot sampling carefully. Insertion sort on tiny ranges often reduces overhead. Median-of-three or larger random samples can improve split quality, but deterministic sampling is not an adversarial worst-case guarantee. Either change alters the measured trace and statistics.
• Choose stability and mutation consciously. The shown algorithms reorder equal-key records. If stable ordering matters, choose a stable algorithm or design a separate stable partition with its associated storage cost. Copy input data when callers need it preserved.

An ordering must be consistent. Floating-point NaN is neither smaller, larger, nor equal under ordinary comparisons, so this integer-oriented branch structure would incorrectly treat it as equal to a pivot. A floating-point version must specify an explicit total ordering and a NaN policy. For records, compare keys consistently and avoid subtraction-based comparators that can overflow on extreme integers.

Reproducibility requires more than recording a seed: record the generator, range-conversion rule, array order, comparison order, and traversal order. A public fixed seed is useful for teaching and regression tests but does not prevent crafted inputs. In production, choose an appropriate generator and fallback strategy for the workload; the correctness invariant should remain valid even if every pivot is poor.

Practice Problems and Real-World Use

Validate sorting against an independently sorted copy and verify identical multiplicities. Validate selection against the sorted copy's $k$-th value, check $A[k]$, verify that earlier values are at most it and later values are at least it, and verify the multiset. Do not require Quickselect's entire output to match a sorted array or another implementation's arrangement.

For exhaustive small tests, enumerate arrays over a tiny alphabet such as $\{-1,0,1\}$ and test every valid rank across several seeds. Add sorted and reverse-sorted distinct arrays, all-equal arrays, alternating extremes, duplicate-heavy data, empty sorts, singleton selection, rejected ranks, and invalid seeds. Instrument partition boundaries to check the four-region invariant after every step; test the random range conversion separately with a small enumerable raw range so that every residue count can be verified exactly.

For further study, Princeton's Quicksort material discusses randomized and three-way partitioning, while MIT's randomized algorithms lecture notes develop the role of randomized pivots and expected running time. Use their analysis alongside the explicit counter definitions here; changing a partition scheme changes its exact operation counts.