= Sorting permutation preservation
{title2=$B_i=A_{\pi(i)}$}
The <output> of a <sorting algorithm> must be a <permutation> of the complete <input> <sequence>. For equal lengths $n$, require a <permutation> $\pi$ of $\{0,\ldots,n-1\}$ such that
$$
B_i=A_{\pi(i)}\qquad(0\leq i<n).
$$
Equivalently, the <input> and <output> have the same <multiset> of complete entries: each entry has the same multiplicity. Equality of the underlying <sets> is insufficient; $(1,1,2)$ and $(1,2,2)$ have the same <set> of values and the same length but different <multisets>. When tracking occurrences rather than contents, retain original identity labels to check that each one is moved exactly once. A swap preserves this <multiset> automatically; an overwrite need not.
Back to article page
