This is my first blog post from a series of blog post where I’ll describe how a new sort algorithm works. This new sorting algorithm is called HOBS ( High Order Bucket Sorting). HOBS has it’s roots in Bitmap Sort, with Bitmap Sort an array can be sort really fast but is very efficient when it has to deal with small numbers. If the numbers are high Bitmap Sort will require too much memory and thus it will be very inefficient from space perspective.

Let’s see how the bitmap works, assuming that we have this array:

int array[6] { 4, 4, 1, 3, 4, 2 };

the bitmap search will allocate another array assuming that the max value in the unsorted array is 10.

int sorted_array[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

After a pass in the unsorted array we have to introduce another array that keep track of how many value are with 1 at position 1, how many values we have with 2 and position 2 and so one.

bs_array = {1, 1, 1, 3, 0, 0, 0, 0, 0, 0};

So for e.g. in the bs_aray we have 1 value of 1, 1 value of 2, 1 value of 3 and 4 value of 4, the rest of the elements of the array are zero since we don’t have other values.

After another pass in the bs_array the sorted array looks like this:

sorted_array = {1, 2, 3, 4, 4, 4 };

In this case the max value in the unsorted array is 4 but if the max value is higher the size of the sorted_array should be at least as big as the max.

With HOBS I manage the fix the space problem complexity, in average my algorithm takes an additional 140 KB.