# Is there an existing algorithm for this type of sorting?

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?

• Radix sort or bucket sort. – Yuval Filmus Jan 13 '19 at 21:32
• Sounds like bucket sort is the one those commenters were thinking of. If you put that in an answer I can accept it :) – Lou Jan 13 '19 at 21:35
• There was a recent development over the insertion sort, that is called the Library sort or gapped insertion sort. That is the way the librarians keep their books. – kelalaka Jan 13 '19 at 22:25

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").