I've come across references to Bill Gates's work on pancake sorting, but I haven't found a clear explanation of the optimized solution attributed to him. Did Gates and Christos Papadimitriou actually develop an algorithm, or did their paper mainly study improved lower bounds for the problem?
2 Answers
The implementation commonly associated with Gates is usually described as a standard greedy pancake-sorting approach: repeatedly find the largest unsorted pancake, flip it into position, and continue. That’s useful, but it may not be the optimized result people expect when they hear about the paper.
Gates worked on the problem with Christos Papadimitriou, and they published a paper about it. Their main contribution was analyzing the problem and improving the lower bounds, rather than presenting a completely different practical sorting implementation.
That matches my reading too—the paper seems focused more on theoretical bounds than on writing out a new optimized algorithm.