Sort key ($k(A_i)$)

A sort key is the value extracted from a complete entry to determine its ordering. Model extraction as a function $k$ into a total order; compare $k(A_i)$ and $k(A_j)$, while moving the complete entries. Ordering sorting records by an age field does not also compare their names. Repeated sort keys are allowed, so this induces equal-key groups even when the complete sorting records differ. Keep the sort key function and the comparison rule fixed throughout a sort; inconsistent comparisons need not admit any sorted result.

A complete entry comprising a sort key together with any associated data. In $(2,A)$, the sort key is $2$ and $A$ stands for the associated data or an identity label. Sorting permutation preservation concerns these complete entries, rather than only their extracted sort keys.