Top-down Synthesis of Sorting Algorithms

Kung-Kiu Lau
Department of Computer Science
University of Manchester
Oxford Road
Manchester M13 9PL

Abstract:
Traditionally sorting algorithms are classified according to their main 
operational characteristic, rather than their underlying logic. More 
recent work in program synthesis has exposed the logic of and hence the
logical relationships between some sorting algorithms. Following the
program synthesis approach, and by using a logic programming system for 
deriving recursive logic procedures from their specifications, we have 
synthesised a large family of sorting algorithms in a strictly top-down 
manner. Such an approach not only produces algorithms which are 
guaranteed to be partially correct, it also provides a family tree
showing clearly the relationships between its members.