What is a Sorting Function?

TY - JOUR

T1 - What is a Sorting Function?

AU - Henglein, Fritz

N1 - Paper id:: doi:10.1016/j.jlap.2008.12.003

PY - 2009

Y1 - 2009

N2 - What is a sorting function—not a sorting function for a given ordering relation, but a sorting function with nothing given?Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: A function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function.We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction.Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.

AB - What is a sorting function—not a sorting function for a given ordering relation, but a sorting function with nothing given?Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: A function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function.We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction.Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.

U2 - 10.1016/j.jlap.2008.12.003

DO - 10.1016/j.jlap.2008.12.003

M3 - Journal article

SN - 2352-2208

VL - 78

SP - 552

EP - 572

JO - Journal of Logic and Algebraic Programming

JF - Journal of Logic and Algebraic Programming

IS - 7

ER -