## Sorting Morphisms

From: "andrew cooke" <andrew@...>

Date: Fri, 22 May 2009 02:41:27 -0400 (CLT)

"Sorting algorithms can be classified in many different ways. The way
presented here is by expressing the algorithms as functional programs and
to classify them by means of their recursion patterns. These patterns on
their turn can be classified as the natural recursion patterns that
destruct or construct a given data-type, the so called cata- and
anamorphisms respectively. We show that the selection of the recursion
pattern can be seen as the major design decision, in most cases leaving no
more room for more decisions in the design of the sorting algorithm. It is
also shown that the use of alternative data structures may lead to new
sorting algorithms."

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3315
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B5EA6DCBA219BAC57854124F31E6A881?doi=10.1.1.51.3315&rep=rep1&type=pdf

Andrew