Sorting

In 1959, as a visiting student at Moscow State University, Tony Hoare worked on machine translation from Russian to English. To look words up efficiently in a dictionary on magnetic tape he first needed to sort them, and the methods he knew were too slow. The algorithm he devised, which partitions the data around a chosen value and then sorts each side, was published in 1961 and described fully in The Computer Journal in 1962. He called it quicksort.

More than sixty years later, variants of it still sit inside the sorting routines of standard libraries. Sorting is the most studied problem in computer science because so much else, from binary search to deduplication to database joins, starts with it.