1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Radix sort or bucket sort. $\endgroup$ – Yuval Filmus Jan 13 at 21:32
  • $\begingroup$ Sounds like bucket sort is the one those commenters were thinking of. If you put that in an answer I can accept it :) $\endgroup$ – Lou Jan 13 at 21:35
  • $\begingroup$ 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. $\endgroup$ – kelalaka Jan 13 at 22:25
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.