3.2 Selection, quickselect, and linear-time sorting

The selection problem asks for one ranked element, whereas sorting asks for the complete order. This distinction lets quickselect discard work that cannot affect the requested rank. Counting sort and LSD radix sort go further: they can cross the comparison-sorting barrier by using structure in the keys, but only under explicit range and digit assumptions.

Motivation

Suppose a list contains millions of values and we need only its median. Sorting will answer the question, but the complete sorted order contains much more information than one median. A useful algorithmic habit is therefore to ask what output the problem actually requires before choosing a familiar routine.

The repository tutorial develops this idea in three stages. Full sorting gives a simple baseline. Partial selection sort stops after placing the first few order statistics. Quickselect reuses quicksort's partition operation but continues on only the side that can contain the target. The linear-time sorting lecture then changes the computational model: bounded integer keys can be counted, and multi-digit keys can be processed one stable digit at a time.

These algorithms solve a static, one-query problem. If many ranks will be queried without updates, sorting once may be reasonable. If insertions and deletions occur between queries, the dynamic-selection tutorial instead points toward a height-balanced search tree augmented with subtree sizes. Its logarithmic guarantee depends on maintaining balance and metadata, so that data-structure implementation belongs with the tree notes; here it serves only as a boundary between static selection and dynamic order statistics.

Definitions

Definition

Selection problem

Given a list $A$ of $n$ keys and an integer $k$ satisfying $1 \le k \le n$, return the kth smallest key. Rank is one-based, while array indices in pseudocode may be zero-based. Duplicate keys are counted with multiplicity: in $[2,2,5]$, the first and second smallest keys are both $2$.

The cases $k=1$ and $k=n$ are the minimum and maximum. Each needs a single scan, so selection cannot have a general lower bound of $\Omega(n\log n)$ in the comparison model. The lower bound later in this note is about producing a complete sorted order, not about finding one rank.

Partial selection sort performs the first $k$ rounds of selection sort. In round $i$, it finds the minimum of the remaining suffix and swaps it into position $i$. It then returns A[k - 1]; it need not physically remove an array element. Its exact number of key comparisons is

$$\sum_{i=0}^{k-1}(n-i-1) =k(n-1)-\frac{k(k-1)}2,$$

which is $O(kn)$. It is linear when $k$ is a fixed constant, but quadratic when $k$ is proportional to $n$.

Definition

Partition contract

For a current subarray of length $m$, Partition returns an index $p$, places the chosen pivot at A[p], and guarantees that every index below $p$ contains a key at most A[p], while every index above $p$ contains a key at least A[p]. Thus the pivot value is a valid key of local rank $p+1$, even when equal keys occur. This final-pivot-index contract is stronger than a routine that returns only a boundary between two regions.

With one-based rank $k$ relative to the current subarray, correct quickselect branching is:

Quickselect(A, m, k):
    require 1 ≤ k ≤ m
    if m == 1: return A[0]
    p = Partition(A, m)          // p is the pivot's final 0-based index
    if k - 1 == p: return A[p]
    if k - 1 is below p: return Quickselect(A[0:p], p, k)
    return Quickselect(A[p+1:m], m-p-1, k-p-1)

The equality branch is essential. On the right, the new rank subtracts the $p$ left-side positions and the pivot itself.

At the start of every recursive call, the invariant is: the current subarray contains the original requested order statistic, and its parameter $k$ is that value's rank within this subarray. The left call preserves $k$ because no smaller positions have been discarded. The right call discards exactly $p+1$ positions, so it uses $k-p-1$. The base case is reachable because an equality return stops at the pivot and either recursive branch is strictly shorter than its parent. A routine returning a Hoare-style boundary rather than the pivot's final index needs a different argument and must not be dropped into this pseudocode unchanged.

Randomized three-way quickselect

The source teaching trace above uses a two-way final-index partition. For the expected-time guarantee on inputs that may contain duplicates, use a separate three-way variant. Choose one current record uniformly at random as the pivot, then partition into strict-less block $L$, equal block $E$, and strict-greater block $G$. With one-based local rank $k$ and $\ell=|L|$, $e=|E|$:

RandomizedQuickselect(A, m, k):
    pivot = key of a uniformly random record in A
    (L, E, G) = ThreeWayPartition(A, pivot)
    if k ≤ |L|:       return RandomizedQuickselect(L, |L|, k)
    if k ≤ |L| + |E|: return pivot
    return RandomizedQuickselect(G, |G|, k-|L|-|E|)

The same recursive-call invariant holds, but the discarded prefix on the greater branch now has size $\ell+e$. Every recursive call uses a strict block, so it is shorter; if all keys are equal, $E$ is the whole input and the algorithm returns after one $\Theta(m)$ partition. This three-way contract is also different from a Hoare boundary and must be implemented and proved on its own terms.

Definition

Stable sorting

A sorting routine is stable if records with equal keys keep their relative input order in the output. Stability matters when a later pass sorts on one part of a compound key and must preserve order established by earlier passes.

Definition

Counting sort

For integer keys in the inclusive range $0,1,\ldots,K$, standard stable counting sort uses $K+1$ counters. It counts frequencies, converts them to prefix counts, and scans the input from right to left while placing records in a separate output array. Its time is $\Theta(n+K)$ and its auxiliary space is $\Theta(n+K)$ when both the output and count arrays are included. This standard stable version is not in-place.

After accumulation, C[x] is the number of records with key at most $x$. During right-to-left placement, --C[x] selects the last unused position in key $x$'s output block. The counters must be initialized to zero, and maximum key $K$ means valid counters C[0] through C[K]: exactly $K+1$ cells.

Definition

LSD radix sort

Let every nonnegative key have $d$ digits in base $b$. Least-significant-digit (LSD) radix sort stably sorts the whole array by digit $0$, then digit $1$, and continues through digit $d-1$. If each pass is stable counting sort on $b$ digit values, the total time is $\Theta(d(n+b))$ and the auxiliary space is $\Theta(n+b)$.

For $B$-bit machine words grouped into $r$-bit digits, $d=\lceil B/r\rceil$ and $b=2^r$, so the cost is $\Theta(\lceil B/r\rceil(n+2^r))$. Larger digits reduce passes but enlarge the counter array; smaller digits use compact counters but scan the array more times.

The word “linear” is therefore conditional. Counting sort is $\Theta(n)$ when $K=O(n)$. LSD radix sort is $\Theta(n)$ when the chosen representation makes $d$ constant and $b=O(n)$, for example fixed-width machine words with a suitable digit size. Negative keys, variable-length representations, or a huge key universe require additional handling rather than an unqualified linear-time claim.

Counting and LSD radix sort copy whole records while using a bounded integer or extracted digit for direct addressing. Stability is therefore about record identity, not visually indistinguishable equal numeric values.

Theorem/Proposition

Theorem

Why quickselect can avoid full sorting

Assume Partition satisfies the final-pivot-index contract. If its returned index is $p$, a target of local rank $p+1$ equals the pivot; a smaller target rank lies in the left subarray; and a larger target rank lies in the right subarray with adjusted rank $k-p-1$. Consequently quickselect needs at most one recursive call after each partition.

Theorem

Decision-tree lower bound for comparison sorting

For arbitrary inputs of $n$ distinct keys, every deterministic comparison-based sorting algorithm has a worst-case execution using $\Omega(n\log n)$ comparisons. This statement assumes that key comparisons are the only way to learn their relative order; it does not apply unchanged when bounded integers can be used as array indices.

Theorem

Correctness of LSD radix sort

After completing stable passes on digits $0,1,\ldots,j$, the array is sorted by the $(j+1)$-digit suffix viewed as a base-$b$ number. Hence, after all $d$ passes, the array is sorted by the complete key.

Proof sketch or proof idea

Quickselect branch correctness and cost

After partitioning, the pivot is in a position it could occupy in a completely sorted current subarray. Every position to its left contains a key no larger, and every position to its right contains a key no smaller. Therefore a target index below $p$ cannot require the right side, and a target index above $p$ cannot require the left side. Equality returns immediately. This proves the one-branch theorem; no assumption that either side is already internally sorted is needed.

Partitioning costs $\Theta(m)$ on a subproblem of size $m$. If every pivot is extreme, the sizes are $n,n-1,\ldots,1$, giving $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. A perfectly balanced shrink gives the useful intuition $n+n/2+n/4+\cdots\lt 2n$, but that geometric series alone is not an average-case proof.

For the randomized three-way variant, assume each call chooses a record uniformly and independently from the current subarray and that comparisons and swaps take constant time. Give equal occurrences arbitrary consecutive ranks in sorted order. With probability at least $1/2$, the chosen record's rank is in the middle half. Its strict-less and strict-greater blocks then both have size at most $3m/4$; the target either returns from the equal block or survives in one of those strict blocks. The expected number of trials before such a shrink is at most two, and all partitions at that size scale cost $O(m)$ in expectation. Summing over geometrically shrinking scales gives expected $O(n)$. The first partition costs $\Omega(n)$ in this model, so the expected time is $\Theta(n)$. All-equal input takes one linear pass, while distinct-key extreme pivots still give a $\Theta(n^2)$ worst case.

Decision-tree lower-bound proof

For $n$ distinct arbitrary keys, all $n!$ relative orders are possible. A deterministic comparison sort can be represented by a binary decision tree: each internal node compares two keys, and each leaf identifies the input permutation. Correctness requires at least $n!$ leaves. A binary tree of height $h$ has at most $2^h$ leaves, so $2^h\ge n!$ and $h\ge\log_2(n!)$. Let $q=\lfloor n/2\rfloor$. The largest $q$ factors in $n!$ are each at least $\lceil n/2\rceil$, so

$$\log_2(n!)\ge \left\lfloor\frac n2\right\rfloor \log_2\!\left(\left\lceil\frac n2\right\rceil\right) =\Omega(n\log n).$$

Thus some input follows a path of that length. Counting and radix sort do not contradict the result: they use digit extraction, arithmetic, and direct array addressing, and they restrict the key representation.

LSD radix invariant

The claim follows by induction on the passes. After digit $0$, stability is irrelevant and the array is sorted by its last digit. Assume it is sorted by digits $0$ through $j-1$. The next stable pass orders records by digit $j$. Records with different digit-$j$ values are put in the correct order by that digit; records with equal digit-$j$ values retain their prior order, which by the induction hypothesis is the order of their lower-digit suffixes. The array is therefore sorted by digits $0$ through $j$. After digit $d-1$, that suffix is the whole key.

Worked examples

Worked example

Partial selection cost

For the tutorial array $[11,6,43,7,14,28,9,2,4,37,18,34,8]$, finding the fourth smallest key by partial selection places $2$, then $4$, then $6$, then $7$ into the first four positions. With $n=13$ and $k=4$, the four suffix scans make $12+11+10+9=42$ comparisons, and A[3] is $7$.

This is substantially less than all $78$ comparisons of a full selection sort on thirteen elements, but the advantage depends on small $k$. For a median-scale rank, $k=\Theta(n)$ and the method becomes quadratic.

Worked example

Quickselect partition trace

Find the second smallest key in $[56,25,37,58,95,19,73,30]$, using the tutorial's first-element pivots.

1. Partition around $56$ to obtain $[19,25,37,30,56,95,73,58]$. The pivot has index $4$, or rank $5$, so rank $2$ lies in the left subarray $[19,25,37,30]$.
2. Partition that subarray around $19$. The pivot has local rank $1$, so move right and adjust the target to $2-1=1$.
3. In $[25,37,30]$, pivot $25$ has local rank $1$. The equality branch returns $25$.

The untouched partitions need not be sorted. The trace also shows why omitting the equality return or forgetting the right-side rank adjustment is a real correctness error.

Worked example

Counting sort from counts to stable placement

Let $A=[0,5,3,2,3,0,5,1,5,2]$ and $K=5$. The six counters for keys $0$ through $5$ are

$C=[2,1,2,2,0,3].$

After prefix accumulation,

$C'=[2,3,5,7,7,10],$

where $C'[i]$ counts keys at most $i$. Scanning $A$ from right to left, place a record of key $x$ at index --C'[x]. For example, the final input key $2$ sees count $5$, decrements it to $4$, and occupies output index $4$. Repeating this operation produces

$B=[0,0,1,2,2,3,3,5,5,5].$

Right-to-left scanning matters when equal keys carry distinct records: the later equal record takes the later available output position, so their input order is preserved. The three phases cost $\Theta(n)$, $\Theta(K+1)$, and $\Theta(n)$, hence $\Theta(n+K)$ overall.

Worked example

Why stability matters in radix sort

Apply base-$10$ LSD radix sort to $[329,457,657,839,436,720,355]$:

1. stable ones-digit pass: $[720,355,436,457,657,329,839]$;
2. stable tens-digit pass: $[720,329,436,839,355,457,657]$;
3. stable hundreds-digit pass: $[329,355,436,457,657,720,839]$.

In the tens pass, for instance, $720$ remains before $329$ among keys with tens digit $2$ because their ones digits were already ordered. An unstable pass could reverse that pair and destroy the lower-digit ordering on which the induction proof depends.

Common mistakes

• Accepting $k=0$ or $k>n$, or mixing one-based ranks with zero-based indices.
• Treating a partition boundary as though it were necessarily the pivot's final index.
• Omitting quickselect's equality return or failing to subtract $p+1$ when recursing right.
• Claiming quickselect is always linear, presenting balanced shrink as an average-case proof without a uniform randomized-pivot model, or omitting the three-way equal block when duplicates are allowed.
• Writing that sorting takes “at least $O(n\log n)$”; use $\Omega$ for the comparison lower bound and state its assumptions.
• Allocating only $K$ counters for the inclusive key range $0,\ldots,K$, or forgetting to initialize all $K+1$ counters to zero.
• Calling the standard stable counting sort in-place, or scanning left to right while using decreasing prefix-count positions.
• Saying every radix-sort organization needs the same stable-pass argument. The theorem here is specifically for whole-array LSD radix sort.
• Quoting $O(1)$ or $O(\log n)$ dynamic-set operations without the required capacity, expected-hashing, or height-balance assumptions.

Summary

• Selection returns one order statistic; sorting returns all rank information.
• Partial selection costs $O(kn)$ and is attractive only when $k$ is small.
• The source two-way final-index trace lets quickselect recurse on one side. The duplicate-safe uniformly randomized three-way variant returns from its equal block and has expected $\Theta(n)$ time. All-equal input is $\Theta(n)$; worst case is $\Theta(n^2)$.
• Comparison sorting of arbitrary distinct keys needs $\Omega(n\log n)$ comparisons in the worst case by the decision-tree proof.
• Stable counting sort on keys $0,\ldots,K$ uses $K+1$ counters, runs in $\Theta(n+K)$, scans right to left for stability, and is not in-place in its standard output-array form.
• LSD radix sort with $d$ base-$b$ digits and stable digit passes runs in $\Theta(d(n+b))$. Its linearity depends on the representation parameters.

Exercises

Checkpoint

Why is full sorting more work than selection?

Compare the requested output.

Solution · Answer

Selection asks for one ranked element. Sorting asks for the complete order of all elements, which contains more information than a single kth item.

Checkpoint

What extra assumption lets counting sort run in linear time?

Think about the count array.

Solution · Answer

The key range must be bounded so that the count array is not larger than a constant multiple of the input size; commonly this is stated as $K=O(n)$.

1. Explain why quickselect recurses on only one partition side, including the equality case.
2. Give a case where partial selection sort is reasonable, and a case where it is not.
3. Explain why LSD radix sort needs a stable digit subroutine.
4. For $n=20$ and $k=5$, compute the exact comparison count of partial selection sort under the suffix-scan implementation.
5. Starting from prefix counts $[2,3,5,7,7,10]$, state where the rightmost key $2$ is placed and what its counter becomes.
6. Explain precisely why counting sort and radix sort do not violate the comparison-sorting lower bound.

Solutions

Solution · Guided solutions

1. Once the pivot's final index is known, the target rank is either the pivot, strictly left, or strictly right. Equality returns; only the relevant side can contain the remaining target.
2. It is reasonable when $k$ is a small constant and only a few minimum-selection rounds are needed. It is poor for $k=\Theta(n)$, such as a median, because its cost becomes quadratic.
3. Stability preserves the ordering created by lower-digit passes among records tied on the current digit; without it, a later pass can scramble earlier digit information.
4. The count is $19+18+17+16+15=85$ comparisons.
5. The value $5$ is decremented to $4$, so the record is placed at zero-based output index $4$.
6. The lower bound assumes arbitrary distinct keys and learns order only through comparisons. Counting and radix sort restrict key representations and also use arithmetic, digit extraction, and direct addressing.