An inverted taxonomy of sorting algorithms

ABSTRACT

An alternative taxonomy (to that of Knuth and others) of sorting algorithms is proposed. It emerges naturally out of a top-down approach to the derivation of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms that suggest this approach. In particular, all sorts are divided into two categories: hardsplit/easyjoin and easysplit/hardjoin. Quicksort and merge sort, respectively, are the canonical examples in these categories. Insertion sort and selection sort are seen to be instances of merge sort and quicksort, respectively, and sinking sort and bubble sort are in-place versions of insertion sort and selection sort. Such an organization introduces new insights into the connections and symmetries among sorting algorithms, and is based on a higher level, more abstract, and conceptually simple basis. It is proposed as an alternative way of understanding, describing, and teaching sorting algorithms.

REFERENCES

• 1: Barstow. D.R. Remarks on "A synthesis of several sorting algorithms" by John Darlington. Acta Inf. 13 (1980). 225-227.
• 2: Darlington. J. A synthesis of several sorting algorithms. Acta Inf. II (1978). 1-30.
• 3: Green, C. and Barstow. D. On program synthesis knowledge. Artif- Intell. 10 (1978). 241-279.
• 4: Horowitz, E., and Sahni. S. Fundamentals of Computer Algorithms. Computer Science Press, Rockville. Md.. 1978.
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Susan Mary Merritt, The role of the high level specification in programming by transformation: specification and transformation by parts, 1982
• 7: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Performance, Theory