What did Bill Gates write his only research paper about?
Bounds for sorting by prefix reversal
Bill Gates’s only research paper is about how many flips it takes to sort a messy stack of pancakes.
Picture a stack of pancakes of different sizes. You can only slide a spatula under one of them and flip everything above it. How many flips does it take to get them neatly sorted, biggest at the bottom?
The authors found a better limit on the number of flips needed than anyone had before, and it stood for about 30 years. One of them was a student called Bill Gates, who went on to do some other things too.
Before the software empire, there were pancakes.