Pigeonhole sorting takes linear time, which is the best possible performance for a sort algorithm since one has to look at all of the objects to be sorted. However, it requires

- that no two objects in the array be identical;
- an invertible function mapping the objects you are sorting to integers within a fixed range (say, 0 to 1000). If an object precedes another, it must map to a smaller number. (If you're sorting integers, just take them as they come.)

The algorithm works as follows.

- Set up an array of initially empty "pigeonholes" the size of the range.
- Go over the original array, putting each object in its pigeonhole.
- Iterate over the pigeonhole array in order, and put elements from non-empty holes back into the original array.

The hidden constant for this algorithm depends critically on the size of the pigeonhole array. If it is too big, steps 1 and 3 will significantly slow down the algorithm.

Sample C code for this algorithm:

void pigeonhole_sort ( int *low , int *high , int minvalue , int maxvalue ) { /* minvalue and maxvalue can also easily be determined within this function */ int count , size = maxvalue - minvalue + 1 , *current ; bool holes[size] ; for ( count = 0 ; count < size ; count++ ) /*Initializing*/ holes[count] = false ; for ( current = low ; current <= high ; current++ ) /*Sorting*/ holes[(*current)-minvalue] = true ; for ( current = low , count = 0 ; count < size ; count++ ) { if ( holes[count] ) { *current = count + minvalue ; current++ ; } } }