Data Structures and Algorithms 
7.4 Bin Sort 
Assume that
For example, if we wish to sort 10^{4} 32bit integers,
then m = 2^{32} and we need 2^{32} operations
(and a rather large memory!).
For n = 10^{4}:
An implementation of bin sort might look like:
#define EMPTY 1 /* Some convenient flag */ void bin_sort( int *a, int *bin, int n ) { int i; /* Precondition: for 0<=i<n : 0 <= a[i] < M */ /* Mark all the bins empty */ for(i=0;i<M;i++) bin[i] = EMPTY; for(i=0;i<n;i++) bin[ a[i] ] = a[i]; } main() { int a[N], bin[M]; /* for all i: 0 <= a[i] < M */ .... /* Place data in a */ bin_sort( a, bin, N );
If there are duplicates, then each bin can be replaced by a linked list. The third step then becomes:
In contrast to the other sorts, which sort in place and don't require additional memory, bin sort requires additional memory for the bins and is a good example of trading space for performance.
so that we would normally use memory rather profligately to obtain performance, memory consumes power and in some circumstances, eg computers in space craft, power might be a higher constraint than performance. 
Having highlighted this constraint, there is a version of bin sort which can sort in place:
#define EMPTY 1 /* Some convenient flag */ void bin_sort( int *a, int n ) { int i; /* Precondition: for 0<=i<n : 0 <= a[i] < n */ for(i=0;i<n;i++) if ( a[i] != i ) SWAP( a[i], a[a[i]] ); }However, this assumes that there are n distinct keys in the range 0 .. n1. In addition to this restriction, the SWAP operation is relatively expensive, so that this version trades space for time.
The bin sorting strategy may appear rather limited, but it can be generalised into a strategy known as Radix sorting.
Bin Sort Animation This animation was written by Woi Ang. 

Please email comments to: morris@ee.uwa.edu.au 
Continue on to Radix sorting  Back to the Table of Contents 