What is a Sorting Function?

Research output: Contribution to journalJournal articlepeer-review

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.

Original languageEnglish
JournalJournal of Logic and Algebraic Programming
Volume78
Issue number7
Pages (from-to)552-572
Number of pages20
ISSN2352-2208
DOIs
Publication statusPublished - 2009

ID: 9700072