Is there an existing algorithm for this type of sorting?

Question

This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted books, and must quickly sort them into alphabetical order.

A number of commenters pointed out that a far more practical method for real-life sorting would be to take the first letter of each book and put it into 26 different piles (an A pile, a B pile, down to a Z pile.) Then use a conventional sorting method (insertion / quick sort etc.) for each of the 26 sub-piles (which would contain around 50 books each, assuming a roughly even distribution of letters. Or you could repeat the same process if the sub-pile is significantly large, sorting the As into ABs, ACs, ADs and so on.

Is there a name of this kind of sorting algorithm?

Answer 1

This is called bucket sort: split your data range into $k$ "buckets" ($O(k)$), put the data into the buckets ($O(n)$), sort each bucket (however you like), then concatenate all the buckets ($O(k)$). If the sorting is faster than $O(n \log n)$, then the whole algorithm runs faster than any comparison-based sort possibly could!

The problem is that it depends on the distribution of the data. If 99% of your book titles start with A, this gives no real benefit at all! And it doesn't work on data that can't be divided into buckets.

A variation of this, "radix sort", is basically the same except in binary (and with some extra recursion). It runs in $O(wn)$, where $w$ is the bit length of your data (the "word size").