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.

Counting sort uses integer sort keys in $\{0,\dots ,K-1\}$ directly as indices into an array of counts. Constant-cost counting and indexing give $O(n+K)$ 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 $K$ term matters when the key range is large.^[ref]

Insertion sort grows a sorted prefix of an array one entry at a time. In the adjacent-swap version, start with position $i=1$, compare its current sort key with the preceding sort key, and swap the complete sorting records only when the right sort key is strictly smaller. Continue leftward until no swap is needed or the entry reaches position zero; then process original position $i+1$. A tie stops the pass. This is the strict comparison and exchange rule in the authored implementation.^[ref]

Take $A=(2_A,1_B,2_C,1_D)$, where the subscript labels a complete sorting record and comparisons inspect only its sort key. Starting from index zero, the complete key-comparison trace is:

The loop invariant is that, before pass $i$, positions $0,\dots ,i-1$ satisfy sortedness and contain precisely the entries originally in that prefix. Moving the next entry left through strictly larger sort keys extends that prefix, and every swap retains sorting permutation preservation. Equal-key entries never cross, giving stable sorting. Each leftward step decreases the position, and each completed pass increases the prefix length, so the algorithm terminates.

With constant-cost key comparisons and swaps, reverse-ordered distinct sort keys cause $1+2+\cdots +(n-1)=n(n-1)/2$ comparisons and swaps. Thus worst-case time complexity is $O(n^2)$ in Big O notation. An already sorted array needs only $n-1$ key comparisons for $n\ge 1$ and no swaps. The adjacent-swap version uses constant auxiliary space complexity. Small or nearly sorted arrays can therefore make insertion sort useful despite its quadratic worst case.