= Sorting algorithm
{title2=$B_0\leq B_1\leq\cdots\leq B_{n-1}$}
{wiki}
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>, require
$$
i<j\ \text{and}\ k(A_i)=k(A_j)\quad\Longrightarrow\quad p(i)<p(j).
$$
Here $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.
Back to article page
