4.5 Design patterns for sorting

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

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.

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

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