# Algorithm Implementation/Sorting/Pigeonhole sort

All the examples currently on this page seem to be implementations of counting sort and not pigeonhole sort. Pigeonhole sort, when sorting a complex data structure with a key, keeps track of all the elements on a certain key (because equal elements are still distinct); rather than just keep a count like counting sort (which is only applicable to simple value types).

## C99

```void pigeonhole_sort(int *low, int *high, int min, int max)
{
/* used to keep track of the size of the list we're sorting */
int count;
/* pointer into the list we're sorting */
int *current;
/* size of range of values in the list (ie, number of pigeonholes we need)*/
const int size = max - min + 1;
/* our array of pigeonholes */
int holes[size];

/* make absolutely certain that the pigeonholes start out empty */
for (int i = 0; i < size; ++i)
holes[i] = 0;

/* Populate the pigeonholes.  */
for (current = low; current <= high; current++)
holes[*current - min] += 1;

/* Put the elements back into the array in order.  */
for (current = low, count = 0; count < size; count++)
while (holes[count]-- > 0)
*current++ = count + min;
}
```

Note that `min` and `max` could also easily be determined within the function.

## Java

```public static void pigeonhole_sort(int[] a)
{
// size of range of values in the list (ie, number of pigeonholes we need)
int min = a, max = a;
for (int x : a) {
min = Math.min(x, min);
max = Math.max(x, max);
}
final int size = max - min + 1;

// our array of pigeonholes
int[] holes = new int[size];

// Populate the pigeonholes.
for (int x : a)
holes[x - min]++;

// Put the elements back into the array in order.
int i = 0;
for (int count = 0; count < size; count++)
while (holes[count]-- > 0)
a[i++] = count + min;
}
```

## PHP

```function pigeon_sort(\$arr)
{
//search min and max
\$min = \$max = \$arr;
foreach (\$arr as \$num)
{       if (\$num < \$min)
\$min = \$num;
if (\$num > \$max)
\$max = \$num;
}

foreach (\$arr as \$num)
\$d[\$num-\$min]++;

for (\$i = 0; \$i <= \$max - \$min; \$i++ )
while (\$d[\$i + \$min]-- > 0)\$res[] = \$i+\$min;
return \$res;
}
```

## Python

```def pigeonhole_sort(a):
# size of range of values in the list (ie, number of pigeonholes we need)
my_min = min(a)
my_max = max(a)
size = my_max - my_min + 1

# our list of pigeonholes
holes =  * size

# Populate the pigeonholes.
for x in a:
assert type(x) is int, "integers only please"
holes[x - my_min] += 1

# Put the elements back into the array in order.
i = 0
for count in xrange(size):
while holes[count] > 0:
holes[count] -= 1
a[i] = count + my_min
i += 1
```