Sorting algorithm ($B_0\le B_1\le \cdots \le B_{n-1}$)

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.