Rice University - Comp 212 - Intermediate Programming

Spring 2006

Lecture #37 -  Design Patterns for Sorting

Background

In  "An Inverted Taxonomy of Sorting Algorithms," Communication of the ACM, Jan. 1985, Volume 28, Number 1, pp. 96-99, Susan Merritt proposed a new taxonomy for comparison-based sorting algorithms.  At the heart of Merritt's thesis is the principle of divide and conquer.  Merritt's thesis is potentially a very powerful method for studying and understanding sorting.  However, the paper did not offer any concrete implementation of the proposed taxonomy.

The following is our object-oriented formulation and implementation of Merritt's taxonomy.

Object-Oriented Sorting

We model comparison-based sorting as an abstract class using the template method design pattern to perform the sort by relegating the splitting and joining of arrays to its concrete subclasses.  Comparison on objects is carried out via an abstract ordering strategy.  This reduces code complexity and simplifies the analyses of the various concrete sorting algorithms.  Performance measurements and visualizations can be added without modifying any code by utilizing the decorator design pattern.  This object-oriented design expresses the essence of sorting and exhibits a concrete way of unifying seemingly disparate sorting algorithms. Unifying sorting under the single abstract principle of divide-and-conquer leads to an across the board simplification of running time analysis.  Treating all sort algorithms uniformly at the same abstract level provides ways to extend and add more capabilities to existing code without modification, facilitating code reuse.

Click here for the link to the published paper and demo code (by D. X. Nguyen and Stephen B. Wong).

PowerPoint Presentation