Fast Sorts

Fast Sorts: A Million Songs to Sort Before Bedtime: Merge Sort, Sorting Without a Second Copy: Quicksort, Can Any Sort Go Faster? The n log n Speed Limit.

Updated

  1. 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.
  2. 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.
  3. 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.