3 ms·
Well, it requires a ton of (virtual) memory for [0, 1e9], so much you can't do it on 32-bit machines. If you can figure out that a particular quicksort/etc subp
by cormacrelf 7y ago
Well, it requires a ton of (virtual) memory for [0, 1e9], so much you can't do it on 32-bit machines. If you can figure out that a particular quicksort/etc subproblem has a pretty small abs(max-min), then cool, go for it, but try to reuse the allocations for other subproblems.
With this memory issue, it's not a general purpose sort, nor does it have subproblems that you can defer to other sorts, so you wouldn't be able to use it as a default in those "glomsorts" anyway. So plugging pathological gaps is a bit irrelevant.
- daniel-cussen 7y agoIt definitely requires a ton of virtual memory, and yes, you can't do 32-bit word sorting on 32-bit machines. There's actually a use case involving 24-bit words where the number of occurrences of each word doesn't matter, and where they necessarily start to cluster after each iteration. So there is a use case (I might add it's tailor-made for this use-case). But you can still e.g. sort database keys which might only have a 26-bit maximum, and it'll take advantage of any clustering that exists in the data, like if in a log you get some customers appearing more often than others, or more frequently in streaks. It also works great when your data is in ranges and you don't want to manually account for this: this will skip that entire empty range in logarithmic time. (Example, all your keys are between 1000-1100 and 5000-6000. The empty range 1100-4999 will be traversed in like 12 steps.)