Happy birthday Quicksort!

Share this page
Tony Hoare

Tony Hoare, the inventor of Quicksort, in 2011. Photo: Rama, CC BY-SA 2.0 FR

There aren't many computer algorithms famous enough to get their very own birthday party, but Quicksort is one of them. Invented by the computer scientist Tony Hoare and published in July 1961, the algorithm's task is to put lists of things into the correct order: numbers in numerical order, words into alphabetical order, or dates into chronological oder. It does this so successfully, it is still hailed as one of the best sorting algorithms and implemented in many programming languages and libraries.

The following articles explore the invention of Quicksort, how it works, and some other aspects of Tony Hoare's work. They are based on a conversation we had with Hoare, who is currently participating in a workshop run by the Isaac Newton Institute for Mathematical Sciences in Cambridge, as well as a talk he gave there. Enjoy!

Starting with bubbles — Hoare tells us how Quicksort started with an idea he had while lying on a sofa, which involved bubbles.

Happy birthday Quicksort! — We explore the famous algorithm itself with lots if intuition and no computer code.

Tony Hoare: Beyond Quicksort — A quick look at some of Hoare's work towards a beautiful new world where computer errors are a thing of the past.

The Verified Software Initiative — In this video talk on the website of the Isaac Newton Institute Hoare talks about his work on making error-free software a reality.

This content is part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI), an international research centre and our neighbour here on the University of Cambridge's maths campus. INI attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.

INI logo

  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • The BloodCounts! project is gearing up towards one of the largest-scale applications yet of machine learning in medicine and healthcare.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.