Sorting algorithms as special cases of a priority queue sort

This paper offers an exercise for revisiting the main sorting algorithms after they have been taught to students. This is done in a way that emphasizes the relationships between them, and shows how considering abstraction and extreme cases can lead to the generation of new algorithms. A number of authors (including textbook authors) have noted particular relationships between algorithms, such as an uneven split in merge sort being equivalent to insertion sort. In this paper we use a flexible priority queue, the d-heap, to derive three common sorting algorithms. We combine this with using a BST as a priority queue, plus prior observations in the literature, to show strong relationships between the main sorting algorithms that appear in textbooks. In the process students are able to revisit a number of algorithms and data structures and explore elegant relationships between them. This approach can also lead to exercises and exam questions that go beyond desk-checking to evaluate students' understanding of these algorithms.