Fast Sorts
Split the deck and merge the piles, or pick a pivot: merge sort and quicksort, why n log n is the speed limit, and what your language's built-in sort does.
Updated
Fast Sorts
- A Million Songs to Sort Before Bedtime: Merge Sort (Journeyman): Sort a million songs by title in seconds instead of all night: why the simple sorts take hundreds of billions of comparisons, what splitting the list in half buys, and the sort built on splitting and merging, merge sort, with its price in memory.
- Sorting Without a Second Copy: Quicksort (Journeyman): Sort 2 million photos by date on a phone that's short of memory: why merge sort's second copy and selection sort's trillions of comparisons both fall short, and the sort that does its work in place, quicksort, with the one bad day you have to guard against.
- Can Any Sort Go Faster? The n log n Speed Limit (Freelancer): Know whether a faster sort can exist before you hunt for one: why a faster machine, a tweaked quicksort or a cleverer comparison can't beat O(n log n) for a sort that compares, and the one kind of data where you can.
In Real Code
- Most Played, Then A to Z: Stable and Built-In Sorts (Journeyman): List songs by artist, then by title, with your language's built-in sort, and keep songs that tie in the order the user chose: why sorting twice scrambles them in C#, and the promise a sort has to make to keep that order, stability.
Exercise: Sort the Music Library
- Exercise: Sort the Music Library (Journeyman): A music app's library view takes a minute to sort 50,000 imported songs, and tied songs swap places between refreshes: write the comparison, a hand-written sort that's fast and keeps ties in order, and the built-in sort to check it against, and let the tests check them, ties and the 50,000 songs included.