3 ms·
Counting sorts are super neat and O(n), if the number of unique items is really small. Imagine a list of all 0s and 1s that you wanted to sort (like 001110101)
by thehappypm 7y ago
Counting sorts are super neat and O(n), if the number of unique items is really small.
Imagine a list of all 0s and 1s that you wanted to sort (like 001110101). Why bother sorting? Just count up how many 0’s and 1’s there are (four 0’s, five 1’s) and generate the sorted list. O(n).
Clearly this doesn’t work when you have real world data to sort, but it is the basis for a radix sort, where you sort a batch of numbers digit-by-digit, giving you O(n*d). Though I think it’s rarely used.
- jeffasinger 7y agoWe did actually get to use it at work, to real performance benefit. We have a leaderboard with a list of users, which is normally a list of users totalling between 2 to 50,0000, but in rare circumstances can be several million. The scores users can achieve are in a rather small range, perhaps only 450k valid different scores, and we were doing this sort on average once every 30 seconds. What we ended up doing was switching to a radix sort when the list of users got to be very long, as it was substantially faster in those cases, making the user experience much better, as the leaderboard was much more up to date for the very large cases.