An Expanded Taxonomy of Sorting Algorithms

I present an expanded taxonomy of sorting algorithms that is based upon Merritt's inverted taxonomy [1] and Lau's logic‐based derivations [2, 3]. The inverted taxonomy was based on a higher level, more abstract, and conceptually simple top‐down approach to sorting than the traditional taxonomy such as that given by Knuth [4], Work done in automatic program synthesis suggested the approach. Sorts were divided into two categories, hardsplit/easyjoin and easysplit/hardjoin, of which quicksort and mergesort are the canonical examples, respectively. Lau's [2, 3] logic‐based derivations strengthen the inverted taxonomy by deriving comparison‐based sorting algorithms that fall into the two categories of hardsplit/easyjoin and easysplit/hardjoin. Moreover, they expand the taxonomy by deriving distributive algorithms in a symmetric way.