The following is our object-oriented formulation and implementation of Merritt's taxonomy.
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, PowerPoint presentation and demo code (by D. X. Nguyen and Stephen B. Wong).