The original version of this story appeared in Quanta Magazine.
Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf. The algorithm addresses something called the library sorting problem (more formally, the “list labeling” problem). The challenge is to devise a strategy for organizing books in some kind of sorted order—alphabetically, for instance—that minimizes how long it takes to place a new book on the shelf.
Imagine, for example, that you keep your books clumped together, leaving empty space on the far right of the shelf. Then, if you add a book by