I've heard that Bill Gates worked on pancake sorting, but I haven't been able to find a clear explanation or implementation of his optimized approach. Did he publish an actual algorithm, or was his work focused on proving better lower bounds for the problem?
2 Answers
The commonly shown implementation is a standard greedy pancake-sort strategy: repeatedly find the largest unsorted pancake and flip it into position. That is related to the topic, but it shouldn’t automatically be treated as Gates’s optimized solution. The important distinction is between the basic algorithm and the research on tighter bounds for the minimum number of flips.
Gates studied the problem with Christos Papadimitriou, and their published work is mainly about improving the lower bounds for pancake sorting. It doesn’t appear to present a complete, practical implementation of an optimized sorting algorithm.
That clears it up—I was expecting a full implementation, but it sounds like the main contribution was theoretical rather than an algorithm you can directly run.