A Logical Inverted Taxonomy Of Sorting Algorithms

S.M. Merritt 
School of Computer Science and Information Systems
Pace University 
1 Martine Avenue & Oxford Road
White Plains, NY 10606 
USA 
merritt@pacevm.dac.pace.edu 

K.K. Lau
Department of Computer Science
University of Manchester
Manchester M13  9PL
UK
kung-kiu@cs.man.ac.uk

Abstract:
Sorting is still one of the most important problems in Computer
Science. Work in transformational programming and automatic program
synthesis provided the insight that led to Merritt's inverted taxonomy
of sorting algorithms, a high-level, top-down, conceptually simple and
symmetric categorization of sorting algorithms.

More recent work in logic-based program synthesis by Lau has produced
a logical taxonomy of sorting algorithms. This provides a logical
basis for the inverted taxonomy and expands it into a logical inverted
taxonomy to include distributive sorting algorithms which can be
derived along with comparison-based algorithms. The inclusion of
distributive algorithms into a unified conceptual framework is new and
significant for a comprehensive perspective on sorting algorithms.

In this paper, we describe both the inverted and the logical
taxonomies and show how the latter strengthens the latter and expands
it into a logical inverted taxonomy of sorting algorithms, a
high-level, top-down, symmetrical paradigm for all sorting algorithms.