Bucket Sorting

By Alexander Toresson

Inspiration to write this came while reading Mario Suvajac's article Fast Byte Sorting Algorithm. Bucket sorting would be much faster in this case, if the number of bytes to sort was just 40+ (wild guess), to make up for the initialization that's needed for bucket sorting.

So, "What is bucket sorting?", you may ask. It's a sorting algorithm which can sort integers with a short range (the range depends on how much memory you want to waste on it) without comparing any of them, and is one of the easiest to understand sorting algos that exist.

First you'd want a table of integers with one entry for every value an integer you want to sort can have. For a byte, that's 256. Depending on the size of the data you'll sort you'd choose different sizes for the integers, though I'd choose 32-bit integers for the table, at least when sorting bytes, just to be sure. It won't use more than 1k anyway. (wow, a rhyme). Then when sorting, you'd first reset the table, so all entries has got the value 0. Then you're ready to process the bytes. For each byte, increase the entry in the table, which has got the same number as the byte's value, by one. For example if the byte's value is 41, table entry 41 would be increased by one. When you've done this with all bytes, you can easily reconstruct a sorted copy of the byte data. (5 bytes with value 0, 10 with value 1, 3 with value 2 etc...). And then you're done.

E-mail me if you don't understand this and I'll try to explain it so you understand.

I'd recommend this type of sorting algo when sorting words and smaller things, though the speed really depends on the number of unique values a variable can have.


* Extremely fast, if you're sorting reasonably large amounts of data which can have a limited number of unique values. No comparisons at all! Each item examined once!


* Uses more memory than most other sorting algorithms.

* Can only sort integers, though you may want to convert your floats into fixed point values to use this method.

Alexander Toresson