= Sortedness
{title2=$k(B_i)\leq k(B_{i+1})$}
For an <output> <sequence> $B$ of length $n$, <sortedness> means
$$
k(B_i)\leq k(B_{i+1})\qquad(0\leq i<n-1)
$$
under the chosen <total order> on <sort keys>. Its <transitivity> also gives $k(B_i)\leq 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.
Back to article page
