Motivation
A sorting algorithm can exploit different kinds of information. Insertion sort benefits when the input is almost ordered. Randomized quicksort avoids depending on one fixed input arrangement, but still has possible slow executions. Counting and radix sorting use integer key structure rather than learning order exclusively through comparisons. A useful analysis must say which advantage is being used and what it costs.
The previous algorithm-design chapter proves merge sort and a comparison lower bound. Here we develop other sorting mechanisms rather than repeating that argument. The main questions are why movement cost depends on inversions, how randomness changes a cost statement, and why stability is essential when sorting a key one digit at a time.
Definitions
Definition 8.1.1
(Records, stability and inversions)
An input is a sequence of records whose keys lie in a totally ordered set. A correct sorting algorithm returns the same records in nondecreasing key order. It is stable if records with equal keys retain their original relative order. An inversion is a pair of positions with . Let be the number of such pairs; equal keys do not form inversions.
A worst-case bound applies to every permitted input and random outcome. An expected bound for a randomized algorithm averages over its internal random choices for a fixed input; it does not assume that the input itself was drawn randomly. A comparison count counts key comparisons. Array access, index arithmetic and moving a fixed-size record are treated as constant-cost operations in the operation model used below.
For counting sort, keys are integers in with . For radix sorting, keys have base- digits with , padded by leading zeros if necessary. Digit access is assumed constant-cost in this model. These assumptions are additional information, not consequences of a total key order.
Theorem/Proposition
Theorem 8.1.2
(Insertion sort is adaptive to inversions)
Insertion sort that shifts earlier records only when their keys are strictly greater than the inserted key is stable and correct. It makes exactly record shifts and takes operations for in an array implementation. Its worst-case cost is , while an already sorted input takes .
Theorem 8.1.3
(Expected comparisons in randomized quicksort)
Suppose the keys are distinct. Each recursive subproblem chooses its pivot uniformly from its own records, and partitioning compares that pivot once with each other record in the subproblem. Let . For , the expected number of key comparisons is
Consequently the expected operation count is for , with linear partition work. The worst case remains .
Theorem 8.1.4
(Stable counting sort and least-significant-digit radix sort)
Counting sort with cumulative endpoint counts and a right-to-left placement scan is stable and correct in time and auxiliary space. Applying a stable digit sort from the least significant digit to the most significant digit sorts fixed-width keys. Using counting sort for each digit gives time and auxiliary space.
Proof sketch or proof idea
Proof
(Insertion sort: correctness, stability and shift count)
Insertion sort processes positions from left to right. Before inserting the next record, the earlier prefix is a sorted permutation of the original prefix. Shift its larger keys right until the inserted key can be placed after all keys at most it. The prefix is again sorted and contains the same records. Induction proves correctness. Equal keys are never shifted past each other, proving stability.
For the shift count, imagine each shift as swapping the inserted record with its immediately preceding larger record. An adjacent swap of an inverted pair removes exactly one inversion. Their relation to any third record does not change the total inversion count, because the swapped records are adjacent. The algorithm ends with no inversions, so the total number of shifts is exactly the original inversion count. Each successful inner comparison causes a shift; each insertion has at most one additional failed key comparison. The outer iterations and placements add linear work, giving both bounds in .
Proof
(Expected comparisons by pairs of ranks)
For quicksort, label the distinct keys by their final ranks . Keys with ranks are compared exactly when the first pivot chosen from ranks is one of the two endpoints. Pivots outside this interval cannot separate the endpoints. An interior pivot separates them permanently; an endpoint pivot compares them directly. Each interval key is equally likely to be its first pivot, so the comparison probability is .
Let an indicator be one when the pair is compared and zero otherwise. A pair is compared at most once because one of its records is then removed as pivot. Linearity of expectation, which does not require independent indicators, gives
The integral bounds show the stated asymptotic growth. Choosing an extreme pivot every time instead gives comparisons, so a quadratic execution remains possible.
Proof X-ray
Which randomness is averaged?
The key move is to count pairs of ranks instead of following the recursion: whether ranks are compared depends only on which of the ranks is chosen as pivot first, since a pivot outside that interval sends both keys to the same side. Uniform pivots make each of those keys equally likely to be first, and distinct keys make ranks well defined and every pivot split strictly. Linearity of expectation then closes the argument without any independence between pair events.
Fix the complete input order and average over pivot choices only. The distinct-key and uniform-pivot hypotheses justify the endpoint probability ; they are not optional details of the calculation.
Proof
(Counting sort and radix sort are correct)
For counting sort, first count each key's frequency and form cumulative endpoints , the number of records whose key is at most . Key belongs in its allotted consecutive block. Scan the input from right to left; place a record of key at output position and decrement . Each placement uses the rightmost still-empty position of that key's block. All records are placed in sorted blocks. Among equal-key records, the rightmost original record is placed farthest right, preserving their order.
For radix sort, after stable passes the records are sorted by their least significant digits. The next pass orders the new digit. Within equal new-digit groups, stability preserves the previous lower-digit order, so the records become sorted by the lowest digits. The zero-pass assertion is vacuous; induction through all digits proves correctness. The time and space bounds follow by adding the counting-sort costs of each pass and reusing storage.
Worked examples
Worked example 8.1.5
(Four inversions, four insertion shifts)
Use keys , with subscripts identifying equal-key records. The first key exceeds all three later keys, giving three inversions; key two exceeds the later , giving one more. Inserting shifts three once; inserting two shifts three once; inserting shifts three and two. The four shifts produce . Strict comparison leaves before , demonstrating stability in addition to sortedness.
Worked example 8.1.6
(Expected cost is not a cost every run attains)
With three distinct keys, a middle-rank pivot has probability and uses two comparisons. An extreme pivot has probability and leads to three comparisons in total. Thus the expectation is , agreeing with . An individual run uses two or three comparisons, never eight-thirds. The noninteger expectation describes an average over executions, not fractional work in one execution.
Worked example 8.1.7
(Endpoint counts and reverse placement)
For keys with universe , frequencies are and cumulative endpoints are . Scanning backwards places key one at position one, at position three, zero at position zero, and at position two. The output is . A forward scan using the same decrementing endpoints would reverse the two records of key two, so scan direction belongs in the stability proof.
Stability is an observable property of records
A bare list of equal numbers can conceal instability because swapping equal numbers does not change the displayed sequence. Distinguishing the records by their original positions makes the property visible. The sorting requirement concerns the key order, while stability concerns a second piece of information carried by each record. A proof should not infer the latter solely from the former.
Stable sorting supports secondary criteria. If records are already ordered by a secondary key, a stable sort by a primary key keeps the secondary order within each primary-key group. This is the exact mechanism used by least-significant-digit radix sorting. It is also why the stable digit-sort requirement cannot be replaced by a vague claim that every pass returns a sorted digit list.
The array indexing convention matters in counting sort as well. Cumulative endpoints are counts, not valid positions in every case. Subtracting one converts the endpoint count into a zero-based position, and then decrementing records the shortened available block. A proof using one-based arrays would have a different placement expression but the same block invariant. Mixing those conventions introduces an off-by-one error that is independent of the mathematics of counting frequencies.
Adaptivity, expectation and worst case answer different questions
Insertion sort's inversion bound applies deterministically to the actual input. If there are few inversions, that specific run is fast. Randomized quicksort's expected bound applies to every fixed distinct-key input, but it averages over internal choices. A rare poor pivot sequence may still be slow. Neither statement implies the other, and neither changes what a worst-case quantifier means.
To expose the dependence on the pivot rule, consider sorted input with a rule that always chooses the first record and a partition that preserves relative order within each recursive part. Every partition leaves one subproblem shorter by only one record. The total partition work is therefore a sum of successively smaller linear costs, producing quadratic growth. Uniform random pivot selection prevents that particular input arrangement from forcing the same bad split every time, but it does not make bad splits impossible.
The expected-time theorem also includes the work needed to partition. It is not enough to choose a pivot quickly if the implementation repeatedly copies records inefficiently or performs superlinear partition work. The stated analysis assumes a linear pass over each subproblem and constant-cost record/key operations. Long strings, arbitrary-precision numbers or expensive comparison functions require an additional cost model.
Equal keys require a different quicksort analysis
The exact pair formula assumes distinct keys, so each record has a unique rank and every pivot separates strictly smaller and larger keys. If all keys are equal and a two-way partition sends all nonpivot records to one side, every call may shrink by only one even with random pivots. The pivot's identity is random, but its key gives no balancing information. The distinct-key theorem cannot be used to declare that execution efficient.
A three-way partition separates keys smaller than, equal to and greater than the pivot, then recurses only on the strict groups. This handles the all-equal input in one linear partition. Establishing a complete expected bound for arbitrary multiplicities requires its own argument; the present exact formula is intentionally limited to distinct keys. The example identifies the missing hypothesis rather than treating duplicates as a small implementation detail.
Counterexample mode
An unstable digit pass can undo earlier work
Take the two-digit keys twelve and eleven. Sorting units digits puts eleven before twelve. Their tens digits are equal. If the tens pass is allowed to reverse equal-digit records, it returns twelve before eleven and destroys the required order. A stable final pass retains the lower-digit ordering. Sorted digits alone do not certify a radix pass sequence.
Why integer sorting does not violate the comparison lower bound
The comparison lower bound describes algorithms that learn the order through comparisons alone. Counting sort reads a key value and uses it to select a count-array entry. That is additional access to the representation. Its time includes the size of the key universe, even when few key values occur. An enormous sparse universe can therefore make counting sort worse than comparison sorting.
Radix sorting distributes the representation cost across digits. Its bound includes the digit count and base size; it is not simply linear for every possible integer input. Increasing the base reduces the number of digits but increases the number of counters that must be initialized at every pass. A complexity claim must retain both parameters and the digit-access assumption.
Concept lensAlgorithmic
Choose the model before comparing bounds
Insertion sort measures disorder, quicksort averages internal randomness, and counting/radix sorting exploit key representation. The same input length does not erase those different parameters. State the key domain, duplicate convention, record-movement cost and randomness before deciding which theorem applies.
Common mistakes
A stable algorithm need not be fast, and a fast algorithm need not be stable. Likewise an expected bound is not a guarantee for every random seed. Randomizing a pivot does not automatically make a poor duplicate-handling rule efficient.
For the inversion analysis, count strict key inequalities at original positions. Equal keys contribute no inversions. The proof counts shifts of existing records, not all assignments including storing the inserted record. The extra placements are included in the linear term of the operation bound.
Common mistake
(Shifting past equal keys)
Shifting while the previous key is at least the inserted key still returns a sorted array, so it looks harmless. On there are no inversions, so strict insertion sort makes no shift. The weak comparison shifts once and returns . The shift count then exceeds and stability is lost.
Common mistake
(Reading counting sort as linear in the number of records)
The bound is , which is linear in only when the key range is . For the two keys and we have but , so counting sort initializes and scans about a million counters to sort two records.
Summary
Insertion sort spends one shift per inversion and is stable under strict shifting. Randomized quicksort's distinct-key expectation follows from endpoint probabilities for rank intervals. Counting sort uses bounded integer keys, and its stable placement rule supports radix induction. Each bound is meaningful only together with its input and operation model.
Exercises
Quick check
(Count inversions in keys (2a,2b,1a,1b). State insertion sort's stable output and number of shifts.)
Subscripts identify records and do not affect their keys.
Solution · Answer
Each of the two key-two records exceeds each of the two later key-one records, giving four inversions. Equal-key pairs do not count. Stable insertion sort outputs and performs four shifts. It also performs linear outer-loop and placement work, so the shift count alone is not the entire operation count.
Quick check
(In randomized quicksort on distinct keys, find the probability that the minimum and maximum are compared, and the probability that adjacent-ranked keys are compared.)
Explain why the answers can differ greatly.
Solution · Answer
For , the extreme ranks are compared exactly when one is the first pivot among all keys, with probability . Adjacent ranks form an interval of size two, so one endpoint is necessarily its first pivot and the comparison probability is one. Intervening ranks can separate distant keys, whereas none can separate adjacent ranks before one becomes a pivot.
Quick check
(Show that sorted distinct input with first-record pivots and order-preserving partition uses comparisons. Explain why this does not contradict the randomized expected theorem.)
Write the sum of partition comparisons and identify the changed hypothesis.
Solution · Answer
Order-preserving partition keeps each recursive subproblem sorted, so its first record is always its smallest key. Partition sizes are , contributing comparisons. Their sum is , including zero for . This pivot rule is deterministic and not uniform within each subproblem. Even a randomized algorithm can produce the same sequence, but its theorem averages over all pivot choices rather than bounding every execution by the expectation.