# Re: Sort using Integrated Histograms

*From*: dcorbit@xxxxxxxxx*Date*: 16 Oct 2006 17:24:45 -0700

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

.

**Follow-Ups**:**Re: Sort using Integrated Histograms***From:*persimmonseven

**References**:**Sort using Integrated Histograms***From:*persimmonseven

- Prev by Date:
**Re: int or long int?** - Next by Date:
**Re: C Source code for Integration & differentiation** - Previous by thread:
**Sort using Integrated Histograms** - Next by thread:
**Re: Sort using Integrated Histograms** - Index(es):