Bytesort vs. BitSort

If you discover that the speed of algorithm is somehow tied to the number of bins such that more bins means slower execution, there might be some benefit. For example, if you use 4 bits, you make twice as many loops, but use 1 32nd of the bins. You'd have to figure out the right number of bins for your situation. I doubt very much the answer will be 2.

Don't do pass bit bit if you wind up with 8 times the number of passes. Think of it in these terms: what does it cost to do each pass multiplied by the number of passes. You'll end up 8 times more passes, which are *more* expensive too. Highly likely to be much slower. ;)

If you're concerned with memory usage, you don't have to have 256 bins times the size of the array you are sorting. You can have number of items array, then have 256 pointers to this array (beginning of each slot).

What you do is one extra pass in the beginning: *count* the slots! Then do a second pass which assigns. It's not worth the effort to dynamically grow the bins ala' std::vector. Either do the counting pass or just have large bins (eg. memory usage vs. memory footprint tradeoff).

Timing with your data will tell what's fastest. Don't forget to compare with the common quicksort for example, it may be a lot slower or a lot faster. It depends on your data too.

Time and check, that way you'll know your options and there's no guessing.

Speedwise, the fewer passes the better as each pass is about the same cost.
For 32-bit numbers, 32 bits at once wont work because it requires 4GB of RAM. 16 bits at once is doable, but in that case it is likely that it will take far more RAM to sort the data than the data itself takes up, which would likely cause too much paging.

A realistic approach is to do 11 bits at once (last phase really only uses half of the table). This takes a more reasonable amount of RAM, and can be good where all memory access takes the same time because you don't have caches to blow out, such as certain embedded devices.
Using 8 bits at once uses a considerably small amount of RAM and appears to be about the best trade-off in most cases, therefore it is most commonly used.

7 bits, 6 bits, or 5 bits at once would be very inefficient due to the last stage not using many bits.

4 bits at once reduces RAM consumption even lower but doubles the number of passes over 8 bits per pass once. The decrease in RAM consumption has become insignificant compared to the time increase.

With 1 bit at a time, you often become able to leave out passes where all values have the same value for a single bit. You still likely end up performing nearly as many passes, but you take not much less RAM than you would for 8 bits at once. In practicality this would be much much slower than quicksort every time, so it not worthwhile.

Woa man. 4 gigs? I can do any size key with [edit]TWO[/edit] arrays of size_bits_of_key dwords and the size of the array to be sorted once more. Then I just sort one array into the other and rotate them and sort again, etc. An even number of rotations and in the end I have the original array, sorted and with a pointer to it.

In fact, I get off cheaper, memory wise, with bitsort. Plus it's simpler to implement, in my view at least. It's the hit on speed of the 8 fold array run throughs and copy&paste elements into the other array that bugs me. And reading each respective bit out of its place for evaluation. You don't have that hassle with full bytes.

10x guys. Still not sure though.

I don't actually copy whole arrays. The sorting process itself does that size_bits_of_key times. I just exchange pointers.