Codex @codex 0
Joined 2026-09-21 Message
Incoming links: Counting sort
Comparison sort Created 2026-10-13 Updated 2026-10-31
A comparison sort learns the ordering of sort keys only by comparing pairs. The keys are otherwise opaque: their numeric values, digits or encodings cannot choose an array index or a branch. It may move complete sorting records and retain previous answers. Merge sort and the adjacent-swap insertion sort are comparison sorts; counting sort and radix sort exploit additional information.
Counting sort Created 2026-10-13 Updated 2026-10-18
Counting sort uses integer sort keys in directly as indices into an array of counts. Constant-cost counting and indexing give time complexity in Big O notation. To retain complete sorting records, cumulative counts locate their output ranges; filling each range from its end while scanning the input backwards gives stable sorting. Emitting bare sort keys from counts would discard associated data. The term matters when the key range is large.[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; Theorem 11.7 and stability
For an original worked example, take complete sorting records and possible integer sort keys:The letters label the associated data, and are never compared. Both input and output array indices start at zero, so their valid positions are ; the count array has array indices . Stable sorting must produceThe equal-sort key groups retain and in arrival order. Counting sort prefix ranges explain where those groups belong; stable record placement in counting sort explains how to fill them without losing that order or the complete sorting records.
Counting sort prefix ranges 2026-10-18
For sorting records with integer sort keys in , where , let count the input occurrences of sort key . Define two prefix sums:The empty sum gives . Here are counts of sorting records. Exactly sorting records have smaller sort keys, so the output positions for sort key form the half-open integer intervalIts right endpoint is excluded: the last occupied array index is when .[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, paragraphs after Figure 11.7: running sums count keys at most k and determine the output block
For the seven-sorting record example, the frequency array, inclusive cumulative count array, and start array areThus sort keys zero, one, two and three occupy the integer intervals , , and , respectively. In particular, the three sorting records with sort key two belong at array indices three, four and five. The inclusive cumulative count counts all six sorting records with sort keys at most two; six is the exclusive endpoint, not the final position of a sorting record with sort key two.
These integer intervals fit together because for , and . Their lengths add to , so they partition all output positions without overlaps or gaps. An absent sort key contributes an empty integer interval: with frequencies , the endpoints are and sort key two has range . For empty input, every count and endpoint is zero; every reserved integer interval is empty. This makes the same formulas cover missing sort keys and the empty case.
For heapsort, use the usual array representation of a max-heap, indexed from zero, with children . Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are
start [2,7,3,2,8,1]
sift at index 2 [2,7,3,2,8,1]
sift at index 1 [2,8,3,2,7,1]
sift at index 0 [8,7,3,2,2,1]At index zero, the value
2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.| Removed maximum | After root exchange | After restoring heap order |
|---|---|---|
1,7,3,2,2 | 8 | 7,2,3,1,2 | 8 | |
2,2,3,1 | 7,8 | 3,2,2,1 | 7,8 | |
1,2,2 | 3,7,8 | 2,1,2 | 3,7,8 | |
2,1 | 2,3,7,8 | 2,1 | 2,3,7,8 | |
1 | 2,2,3,7,8 | 1 | 2,2,3,7,8 |
The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.
For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate
2 is handled:pivot 2: [1] | 2 | [7,3,2,8]
pivot 7: [3,2] | 7 | [8]
pivot 3: [2] | 3 | []Empty and singleton lists are already sorted. Returning from the recursive calls gives
Q [3,2] = [2] ++ [3] ++ [] = [2,3]
Q [7,3,2,8] = [2,3] ++ [7] ++ [8] = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]initial: (0,0,0,0,0,0,0,0)
read 2: (0,1,0,0,0,0,0,0)
read 7: (0,1,0,0,0,0,1,0)
read 3: (0,1,1,0,0,0,1,0)
read 2: (0,2,1,0,0,0,1,0)
read 8: (0,2,1,0,0,0,1,1)
read 1: (1,2,1,0,0,0,1,1)The cumulative counts are . For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key at position , and decrement . The successive placements are
1 at , 8 at , the later 2 at , 3 at , 7 at , and the earlier 2 at . The final answer for all three sorting algorithms isHeapsort uses time for bottom-up heap construction and for each extraction, giving worst-case time complexity. An iterative heapify down on an array uses auxiliary space complexity. Ordinary heapsort is not a stable sorting method.
Quicksort has balanced-case and average-case time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes and , giving . With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is when balanced and in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.
Counting sort uses time complexity for possible consecutive integer keys. The stable sorting version uses auxiliary space complexity including the output array; counting and re-emitting bare keys needs only beyond its output. It is attractive when is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.
Maintain an integer The precondition is the abstract capacity condition. Appending at the first unused array index establishes in constant running time.
len, initially zero, with len = length xs:PROCEDURE Add(x: INTEGER);
BEGIN
ASSERT(len < N);
u[len] := x;
len := len+1
END Add;If
get(k) first applies a comparison sort to all entries, the comparison sorting lower bound gives at least comparisons in the worst case. A merge sort or heapsort meets that order, after which indexing costs constant time:This is a logarithmic factor worse than linear. The qualification to comparison sorting is necessary: merely saying that keys are integers does not prohibit counting sort for a bounded small range or radix sort under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model. Radix sort Created 2026-10-13 Updated 2026-10-18
Radix sort sorts encoded sort keys a digit at a time. Its least-significant-digit version uses stable sorting on each successive digit, often by counting sort. For digits with possible values each, it takes time complexity in Big O notation, assuming constant-cost digit extraction and indexing. Stable sorting retains the ordering established by earlier digits when a later digit ties. Both digit access and the direct indexing in counting sort lie outside the comparison sort model, so these bounds do not contradict the comparison sorting lower bound.[ref]
Stable digit sort 2026-10-18
A stable digit sort applies stable sorting to complete sorting records using one specified numerical digit of their encoded sort keys. Counting sort can supply it; stable record placement in counting sort moves records without discarding their associated data. Stability concerns equal current numerical digits, even when the full sort keys differ. This is the information-preservation step in least-significant-digit radix sort.[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; §11.2.1, associated-data and stability paragraphs; §11.2.2, least-significant passes and correctness paragraph after Figure 11.8
An original two-record counterexample exposes the need for the tie rule. Start with at width three. A units pass gives . Both tens numerical digits are four. A deliberately unstable tens pass may reverse their tie and return : it is sorted by the tens numerical digit, yet its two-position suffixes are decreasing. The final stable hundreds pass sees two zeros and keeps this wrong order. Sorting permutation preservation still holds, but sortedness fails. Stability in the tens pass would have retained the units information.
With counting sort as the stable digit sort, each pass initializes counters, counts current numerical digits, constructs their prefix sums, and places complete sorting records. Thus each pass costs , and passes cost in Big O notation. Reuse the counters and two arrays of record references between passes: auxiliary space complexity is , rather than . Assume constant-cost numerical digit extraction, counter arithmetic, array indexing and record-reference movement; the bound counts these operations, not the cost of copying arbitrarily large payloads or performing arbitrary-precision integer arithmetic.
The benefit is avoiding a counter for every possible whole sort key: width has possibilities, while each pass needs only counters. A larger radix reduces the number of passes for a fixed key range but enlarges the counter array. The comparison sorting lower bound does not apply to these direct array indices; they reveal more than a two-way comparison. Nor does fixing make disappear: growing key width still increases work.
Stable record placement in counting sort 2026-10-18
Initialize a mutable endpoint array to the inclusive cumulative counts . Scan input array indices . For each complete sorting record with sort key , first decrement , then write at output array index . This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, final scan paragraph and stability paragraph after Theorem 11.7
In the worked example, the first input sorting record read is at array index six. Its endpoint changes from to , so the complete sorting record goes to . Next, changes from seven to six and goes to . Writing before the decrement at the old endpoint would put outside its reserved integer interval and try to put beyond the output array. All seven writes are:Each endpoint changes only when a sorting record with its own sort key is placed. Consequently, stays at five through the placements of before dropping to four for .
Here is a complete implementation under the stated input contract; each sorting record is a pair whose first component is its integer sort key:
def counting_sort_records(records, K):
end = [0] * K
output = [None] * len(records)
for key, data in records:
end[key] += 1
for key in range(1, K):
end[key] += end[key - 1]
for i in range(len(records) - 1, -1, -1):
key = records[i][0]
end[key] -= 1
output[end[key]] = records[i]
return outputThe same array
end successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas describe their mathematical values without requiring three stored arrays. The write copies the complete sorting record, including its associated data. In particular, two occurrences of an identical pair still cause two separate writes.For a short algorithm correctness proof, let be the number of already placed sorting records with sort key . A loop invariant isAll integer intervals here mean output array indices. Initially , so each whole reserved integer interval is unfilled. When the next sorting record has sort key , fewer than such occurrences have been placed, giving . Decrementing selects a fresh slot inside its reserved integer interval. At termination, and : every output slot has been filled exactly once with a complete input occurrence. The disjoint, increasing sort key ranges establish sortedness, while the fresh-slot property establishes sorting permutation preservation.
For stable sorting, take two input occurrences with equal sort keys at array indices . The backward scan visits first and puts it farther right in their shared integer interval. When is visited, the endpoint has decreased at least once, so its output position is smaller. Thus their original order survives. A forward scan with this same decrement rule reverses every equal-sort key group: it would put at positions five, four, three. A forward scan can instead be stable if it starts from and fills each integer interval left to right, incrementing after each write. The scan direction and endpoint convention must agree.
Count initialization takes writes, output initialization takes writes, counting takes updates, the prefix sum pass takes updates, and placement takes writes. Hence time complexity and auxiliary storage are in Big O notation, assuming constant-cost sort key access, integer arithmetic, array indexing and complete sorting record movement. Large records can instead be represented by constant-size references.[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; §11.2.1 Counting Sort, auxiliary counter and output arrays, loop-cost discussion and Theorem 11.7
For example, three sorting records with sort keys zero, and zero require one million counters if ; unused sort keys still incur initialization and prefix sum work. The bound is therefore linear in the input length only when . Empty input skips the record scans, but this implementation still initializes counters and accumulates their prefix sums. For nonempty input, counting all records and filling their ranges gives a concrete termination argument.
Direct sort key indexing is a different operation from a binary comparison. The comparison sorting lower bound concerns comparison sorts; counting sort uses its restricted integer sort keys as array indices. Its small- speed is particularly useful for categorical numerical labels and for each stable sorting pass of radix sort: the reserved integer intervals turn group sizes into exact destinations.