Knuth’s coverage of polyphase merge sort is fantastic.
A couple years ago, while still in school, I took a class on file systems (sadly, that was the last quarter the class was offered. It’s now been replaced with an “Advanced Operating Systems” class), and we learned and were required to know the details of polyphase merge sort. I didn’t feel like I understood it particularly well, so a friend and I searched through the Computer Science and Engineering Club’s copies of Knuth (which had been only recently donated by a retiring professor), and found his materials on polyphase merge sort. Not only did I come out of it with a better understanding of the algorithm, but I also had an appreciation for the relationship between the number of runs in polyphase merge sort and the notion of higher-order Fibonacci numbers, which Knuth discusses in the midst of his explanation of the algorithm.
Knuth’s coverage of polyphase merge sort is fantastic.
A couple years ago, while still in school, I took a class on file systems (sadly, that was the last quarter the class was offered. It’s now been replaced with an “Advanced Operating Systems” class), and we learned and were required to know the details of polyphase merge sort. I didn’t feel like I understood it particularly well, so a friend and I searched through the Computer Science and Engineering Club’s copies of Knuth (which had been only recently donated by a retiring professor), and found his materials on polyphase merge sort. Not only did I come out of it with a better understanding of the algorithm, but I also had an appreciation for the relationship between the number of runs in polyphase merge sort and the notion of higher-order Fibonacci numbers, which Knuth discusses in the midst of his explanation of the algorithm.