The following discussion is based on the the SIGCSE 2001 paper by Nguyen and Wong, "Design Patterns for Sorting" D. Nguyen and S. Wong, “Design Patterns for Sorting,” SIGCSE Bulletin 33:1, March 2001, 263-267 .
Merritt's thesis
In 1985, Susan Merritt proposed that all comparison-based sorting could be viewed as “Divide and Conquer” algorithms. S. Merritt, "An Inverted Taxonomy of Sorting Algorithms," Comm. of the ACM, Jan. 1985, Volume 28, Number 1, pp. 96-99 That is, sorting could be thought of as a process wherein one first "divides" the unsorted pile of whatever needs to sorted into smaller piles and then "conquers" them by sorting those smaller piles. Finally, one has to take the the smaller, now sorted piles and recombines them into a single, now-sorted pile.We thus end up with a recursive definition of sorting:
- To sort a pile:
- Split the pile into smaller piles
- Sort the smaller piles
- Join the sorted smaller piles into a single pile
We can see Merritt's recursive notion of sorting as a split-sort-join process in a pictoral manner by considering the general sorting process as a "black box" process that takes an unsorted set and returns a sorted set. Merritt's thesis thus contends that this sorting process can be described as a splitting followed by a sorting of the smaller pieces followed by a joining of the sorted pieces. The smaller sorting process can thus be similarly described. The base case of this recursive process is when the set has been reduced to a single element, upon which the sorting process cannot be broken down any more as it is a trivial no-op.
Animation of the merritt sorting thesis (click the "reveal more" button)
Merritt's thesis is potentially a very powerful method for studying and understanding sorting. In addition, Merritt's abstract characterization of sorting exhibits much object-oriented (OO) flavor and can be described in terms of OO concepts.
Capturing the abstraction
So, how do we capture the abstraction of sorting as described by Merritt? Fundamentally, we have to recognize that the above description of sorting contains two distinct parts: the invariant process of splitting into sub-piles, sorting the sub-piles and joining the sub-piles, and the variant processes of the actual splitting and joining algorithms used.Here, we will restrict ourselves to the process of sorting an array of objects, in-place -- that is, the original array is mutated from unsorted to sorted (as opposed to returning a new array of sorted values and leaving the original untouched). The
Comparator object used to compare objects will be given to the sorter's constructor.
Abstract sorter class
sort method, which performs the split-sort-sort-join process as described by Merritt. The variant processes are represented by the abstract
split and
join methods, whose exact behaviors are indeterminate at this time.