The algorithm works as follows.
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++ ; } } }