A 30 year sorting algorithm saga: from 250k to 14GB in one minute

Microsoft Research busted through the world record for sorting an unprecedented amount of data in under one minute, with a new sorting technique called MinuteSort (with flat datacenter storage). The Microsoft Research team sorted the equivalent of two 100-byte data records for every human being on the planet.

That’s a rough equivalent of a short email message, for example, this series of 1’s represents 200 bytes:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111111

This is 200 bytes of a plain text message you might send in an email.

How much wood could a woodchuck chuck if a woodchuck could chuck wood?
Good woodchucks chuck much.

Multiply that by the population of planet Earth, currently at around 7 BILLION, and the result is 1,400,000,000,000 bytes, or over 14GB in one minute.

That’s a lot of data to wade through, and sorting hasn’t always been so fast and sexy. Take a look at this scan of an ancient TI-99 programming magazine article from 1983 on five popular sorting algorithms, some still used today.

  • Bubble Sort
  • Shell Sort
  • Selection Sort
  • Heap Sort
  • Quick Sort

Here’s a sampling of the article, page 1 & 2 (Download the complete 5 pages)

 

Ti-1_2ti-1a_2

 

Turn to the last page or the article and you can see that in 1983 the Quick Sort, wins the honor of sorting roughly 250k in about 1 minute and the Bubble sort can run equivalent of the 200 byte sample sample above in about 6 minutes (ouch).

image_12

How times have changed.

Sorting basics from Carnegie Mellon http://www.cs.cmu.edu/~adityaa/211/Lecture12AG.pdf [pdf]

Download the complete article

Big congrats to the awesome team at Microsoft Research! 100 points and a Geritol if you are old enough to have used a TI-99 or have read this magazine.