- that no two objects in the array be identical;
- an invertible function mapping the objects you are sorting to integers within a small range (say, 0 to 1000). The range must be limited to some constant times the number of elements that is being sorted to achieve the linear running time. Pigeonhole sort orders the elements by the result of this mapping.

- 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.

Pigeonhole sort is rarely used as the requirements are rarely met and other, more flexible, sorting algorithms are easier to use.

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++ ; } } }