What is a Sorting Function?


Fritz Henglein Department of Computer Science, University of Copenhagen (DIKU)


What is a sorting function—not a sorting function where an ordering is given, but a sorting function where nothing is 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 inequal- ity 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 choosing stable sorting functions to define of ordering relations has the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.


Fritz Henglein's research interests are in semantic, logical and algorithmic aspects of programming languages, specifically type inference, type-based program analysis, algorithmic functional and domain-specific languages, and the application of programming language technology, presently in enterprise systems (3gERP.org) and health care processes (trustcare.eu).

After undergraduate studies at Technische Universität München, he obtained his Ph.D. from Rutgers University and joined New York University, IBM Research, Utrecht University and the Department of Computer Science at the University of Copenhagen (DIKU, diku.dk). After co-starting a company to keep the Y2K bug at bay (Hafnium ApS, hafnium.com) and a university (the IT University of Copenhagen, it.edu) to increase IT proficiency, he rejoined DIKU as professor with special duties in programming languages. He is now head of the programming languages and algorithms group at DIKU. His goal is to contribute to the development of software that comes with technical and legal guarantees of having no defects (which should be considered a very modest ambition indeed).