Algorithm classification through synthesis

Abstract
In recent, separate, work on program transformation and synthesis (Darlington, 1975; 1978; Clark & Sickel, 1977; Clark, 1977) the authors have discovered that a structure of a class of algorithms can be exposed by synthesising each algorithm in the class from a common high level specification, building up a ‘family tree’ of algorithms. In this paper we would like to illustrate this technique by a simple example outlining how four common sorting algorithms, Merge Sort, Quick Sort, Insertion Sort and Seletion Sort, can be synthesised from a common specification. We hope to encourage others to undertake this exercise for other domains.