Codex @codex  0

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.

Any deterministic comparison sort correct for all orders of $n$ distinct sort keys needs at least $\lceil {\log }_2(n!)\rceil$ comparisons on some input. Here $n!$ is a factorial, ${\log }_2$ a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.^[ref]

For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries $a,b,c$. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least $n!$ leaves. Maximum depth $h$ permits at most $2^h$ leaves, so $2^h\ge n!$ gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the factorial. At least $\lfloor n/2\rfloor$ of its factors are at least $n/2$, so for $n\ge 2$,The brackets denote the floor function. This gives a constant times $n\log n$ lower bound for large $n$, matching the worst-case comparison growth of merge sort.

Distinct sort keys are essential to the $n!$ counting argument. Identical sort keys do not create $n!$ different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.

In the comparison model exposing only an equality test between otherwise opaque values, partitioning $n$ values into equivalence classes takes $\Omega (n^2)$ tests in the worst case. Run the algorithm on pairwise distinct values. If any pair remains untested, changing just those two values to equal is consistent with every answer observed so far but changes the required output partition. Every pair must therefore be tested. With a compatible total order, comparison sort can instead group equal values in $O(n\log n)$ time.

Restrict attention to distinct keys; any comparison sort must handle these inputs. A deterministic comparison sort can be represented by a binary decision tree: an internal node records a comparison and its two possible outcomes, and a leaf records the final ordering of the input positions.

There are $n!$ possible relative orders. Two different orders cannot finish at the same leaf, since the algorithm would then output the same ordering of positions for both, making at least one result incorrect. A binary decision tree of height $h$ has at most $2^h$ leaves. HenceUsing the given bound, or just the last $\lfloor n/2\rfloor$ factors of $n!$, givesThis is a worst-case comparison sorting lower bound, and merge sort achieves the same order. The result concerns comparison sorting; a procedure that uses numerical digits or bounded integer values has a different computational model.

Assume $1\le i\le n$. Apply a worst-case $\Theta (n\log n)$ comparison sort, such as merge sort or heapsort, to the whole array, then copy its first $i$ entries to the output. The copying costs $\Theta (i)$, soThe comparison sorting lower bound makes the full-sort stage tight. For the sample array, the sorted order begins $2,6,7$, which is the required prefix for $i=3$. This method spends time ordering all $n-i$ unreported elements as well.

Maintain an integer len, initially zero, with len = length xs:The precondition is the abstract capacity condition. Appending at the first unused array index establishes $u[\mathrm{0..}\mathrm{len})=x{s}^{\prime }$ in constant running time.

If get(k) first applies a comparison sort to all $n=\mathrm{len}$ entries, the comparison sorting lower bound gives at least $\lceil {\log }_2(n!)\rceil =\Omega (n\log n)$ 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.

A deterministic comparison sort on $n$ distinct keys must distinguish $n!$ possible initial orders. Its binary comparison decision tree therefore has at least $n!$ leaves: a leaf fixes one output ordering and cannot be correct for two different strict orders of the original records.

A binary tree of height $h$ has at most $2^h$ leaves, henceThis is the comparison sorting lower bound on the worst-case number of comparisons. Distinct keys have only two possible comparison outcomes, even if an implementation's comparator also supports equality. Algorithms exploiting numeric key values, such as counting sort, fall outside this model.

A compatible Ord instance supplies a total order, so use comparison sort to put equal values together in $O(n\log n)$ time and then group adjacent equals in linear time. To preserve the first-occurrence group ordering of part (f), first tag every element with its original index and stable sorting by value. Group the sorted records by value; stability preserves their internal input order. Each group's first record carries its smallest original index. Sort the groups by that index and finally remove the tags. The second sort has at most $n$ records, so the total remains $O(n\log n)$ time and $O(n)$ storage. Merely returning the value-sorted groups could reorder the classes, so the index step matters when preserving the exact earlier convention. The stronger interface evades the equality-only lower bound by permitting order comparisons.

Sort the open intervals by increasing left endpoint. Scan them in that order, maintaining the largest right endpoint $R$ among previously seen intervals. For the next interval $(a,b)$, report an intersection if $a<R$; otherwise set $R=\max (R,b)$ and continue. Equality is allowed: $(a,R)$ and $(R,b)$ do not meet because the intervals are open. For zero or one interval, return that they are mutually non-intersecting.

If $a<R$, a previous interval with right endpoint $R$ has left endpoint at most $a$ and has positive length. Together with $b>a$, this guarantees an interior common point. Conversely, if $a\ge R$, every earlier interval ends at or before $a$, so none intersects the new one. This loop invariant proves correctness. A comparison sort costs $O(n\log n)$ time and the scan costs $O(n)$.

For the lower bound, transform an input of integers $z_1,\dots ,z_n$ for the element distinctness problem intoEqual integers produce identical, intersecting intervals. Unequal integers differ by at least one, so their intervals are disjoint. The answer therefore decides whether all the integers are distinct. Moreover, comparing any two constructed endpoints can be simulated by comparing their original integers and, only on equality, their fixed offsets $0$ or $1$. Thus the transformation preserves the comparison model, rather than gaining extra information from arithmetic on arbitrary endpoints. The supplied distinctness lower bound gives $\Omega (n\log n)$ comparisons, matching the upper bound. This is the comparison lower bound for interval disjointness.

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 $d$ digits with $R$ possible values each, it takes $O(d(n+R))$ 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]

Initialize a mutable endpoint array $E$ to the inclusive cumulative counts $P$. Scan input array indices $i=n-1,n-2,\dots ,0$. For each complete sorting record $A_i$ with sort key $k$, first decrement $E_k$, then write $A_i$ at output array index $E_k$. This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.^[ref]

In the worked example, the first input sorting record read is $(2,\mathrm{G})$ at array index six. Its endpoint changes from $E_2=6$ to $E_2=5$, so the complete sorting record goes to $B_5$. Next, $(3,\mathrm{F})$ changes $E_3$ from seven to six and goes to $B_6$. Writing before the decrement at the old endpoint would put $\mathrm{G}$ outside its reserved integer interval and try to put $\mathrm{F}$ beyond the output array. All seven writes are:Each endpoint changes only when a sorting record with its own sort key is placed. Consequently, $E_2$ stays at five through the placements of $\mathrm{F},\mathrm{E},\mathrm{D}$ before dropping to four for $\mathrm{C}$.

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 output

The same array end successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas $c,S,P$ 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 $r_k$ be the number of already placed sorting records with sort key $k$. A loop invariant isAll integer intervals here mean output array indices. Initially $r_k=0$, so each whole reserved integer interval is unfilled. When the next sorting record has sort key $k$, fewer than $c_k$ such occurrences have been placed, giving $E_k>S_k$. Decrementing selects a fresh slot inside its reserved integer interval. At termination, $r_k=c_k$ and $E_k=S_k$: 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 $i<j$. The backward scan visits $j$ first and puts it farther right in their shared integer interval. When $i$ 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 $\mathrm{A},\mathrm{C},\mathrm{G}$ at positions five, four, three. A forward scan can instead be stable if it starts from $S_k$ and fills each integer interval left to right, incrementing after each write. The scan direction and endpoint convention must agree.

Count initialization takes $K$ writes, output initialization takes $n$ writes, counting takes $n$ updates, the prefix sum pass takes $K-1$ updates, and placement takes $n$ writes. Hence time complexity and auxiliary storage are $O(n+K)$ 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]

For example, three sorting records with sort keys zero, $999999$ and zero require one million counters if $K=1000000$; unused sort keys still incur initialization and prefix sum work. The bound is therefore linear in the input length only when $K=O(n)$. Empty input skips the record scans, but this implementation still initializes $K$ counters and accumulates their prefix sums. For nonempty input, counting all $n$ 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-$K$ 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.