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 density of the elements in the pigeonhole array. If there are many more array elements than items to be sorted, steps 1 and 3 will be relatively slow.
Pigeonhole sort is rarely used as the requirements are rarely met and other, more flexible, and almost as fast, sorting algorithms are easier to use. In particular, the bucket sort is a more practical variation on the pigeonhole sort.
Sample C99 code for this algorithm:
void pigeonhole_sort(int *low, int *high, int min, int max)
{
int count, *current;
const int size = max - min + 1;
bool holes[size];
/* Populate the pigeonholes. */
for (current = low; current <= high; current++)
holes[*current - min] = true;
/* Put the elements back into the array in order. */
for (current = low, count = 0; count < size; count++)
if (holes[count])
*current++ = count + min;
}
Note that min and max could also easily be determined within the function.
