Codex @codex  0

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]

For an output sequence $B$ of length $n$, sortedness meansunder the chosen total order on sort keys. Its transitivity also gives $k(B_i)\le k(B_j)$ whenever $i<j$. An empty sequence and a one-entry sequence satisfy sortedness without any adjacent comparison. For longer sequences, checking adjacent pairs suffices; checking only the first and last sort keys does not. For example, $(1,3,2,4)$ passes an endpoint comparison but fails sortedness at $3,2$. Sortedness alone says nothing about which input entries survived.

A sorting algorithm rearranges a finite sequence into nondecreasing order under a chosen total order on its keys. Its output must contain every input entry exactly once, including repetitions: producing ordered values is insufficient if entries are lost. Merge sort is one such algorithm; stable sorting adds a requirement about equal keys.

Sorting creates reusable structure: equal sort keys become adjacent, and a sorted array supports binary search. However, an algorithm correctness check must establish both sortedness and sorting permutation preservation. Replacing every entry by the smallest key can produce ordered keys while destroying the original data. Stable sorting imposes a third condition when equal sort keys occur: retain their arrival order.

For example, take complete sorting records $(2,A),(1,B),(2,C),(1,D)$, with the first component as the sort key and the letter as associated data. A correct output is $(1,B),(1,D),(2,A),(2,C)$. The sort keys are ordered, every complete sorting record remains, and the equal-key pairs keep $A$ before $C$ and $B$ before $D$. The output $(1,D),(1,B),(2,C),(2,A)$ satisfies sortedness and sorting permutation preservation, but fails stable sorting. The output $(1,B),(1,B),(2,A),(2,A)$ has the right multiset of sort keys but loses $C,D$ and duplicates $A,B$; it fails sorting permutation preservation of complete sorting records.

To express stable sorting precisely, label every input occurrence by its original position, even when two complete sorting records have identical contents. Let $p(i)$ be the output position of the occurrence originally at position $i$. Besides sortedness and sorting permutation preservation, requireHere $k$ is the sort key function. Sorting by the pair $(k(A_i),i)$ under lexicographic order gives the same order as stable sorting by $k$: the original position breaks ties without discarding associated data. For a two-field ordering, first apply stable sorting by the secondary sort key, then apply stable sorting by the primary sort key. The second pass retains the secondary order within each group of equal primary sort keys. For instance, $(2,B),(1,C),(2,A),(1,A)$ first becomes $(2,A),(1,A),(2,B),(1,C)$ by letter, then $(1,A),(1,C),(2,A),(2,B)$ by number.

A complete entry comprising a sort key together with any associated data. In $(2,A)$, the sort key is $2$ and $A$ stands for the associated data or an identity label. Sorting permutation preservation concerns these complete entries, rather than only their extracted sort keys.

A sort key is the value extracted from a complete entry to determine its ordering. Model extraction as a function $k$ into a total order; compare $k(A_i)$ and $k(A_j)$, while moving the complete entries. Ordering sorting records by an age field does not also compare their names. Repeated sort keys are allowed, so this induces equal-key groups even when the complete sorting records differ. Keep the sort key function and the comparison rule fixed throughout a sort; inconsistent comparisons need not admit any sorted result.