Re: Sort using Integrated Histograms




persimmonseven@xxxxxxxx wrote:
Here is an algorithm I am working on at the moment. I don't suppose it
is novel as it is very simple.
The nice thing is it sorts in linear time.

I show how to sort 32 bit unsigned integers. The algorithm is easily
adapted to signed intergers and floating point numbers.

First create 4 histogram tables with 256 entries in each.
Go through the numbers to be sorted in turn extracting the lowest 8
bits, the low-mid 8 bits, the high-mid 8 bits, and the highest 8 bits
adding 1 to the relevant entry in the corresponding histogram table.
Next you shift the entries in the histograms forward by one. Hence
the entry for 0 will have been shifted to the entry for 1. The entry
for 1 will have been shifted to the entry for 2 and so on.
Put 0 in the entry for 0.
Next you integrate the histograms: Add the entry for 1 to the entry
for 2, add the updated entry for 2 to the entry for 3 and so on.
The histogram entries have now become position pointers.
Next you partially sort the numbers by their lowest 8 bits and the
corresponding (altered) histogram: For each number in turn you look in
the entry indicated by the 8 bits and move the number to the indicated
position in a new array. You then add 1 to the position pointer in the
entry.
The result is a parially sorted list of numbers.
You next repeat the process with the parially sorted list, the low-mid
8 bits and the corresponding (altered) histogram. And so on with the
high-mid 8 bits and the highest 8 bits. Done!

You can of course use different numbers of bits and histogram tables
depending on what is best.

Sean O'Connor 15 October 2006

Your algorithm has another name:
LSD Radix sort.
http://www.google.com/search?hl=en&q=lsd+radix+sort

.