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)
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).
How times have changed.
Sorting basics from Carnegie Mellon http://www.cs.cmu.edu/~adityaa/211/Lecture12AG.pdf [pdf]
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.
Rachel Appel 