Algorithm Implementation/Sorting/Pigeonhole sort

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[0], max = a[0]; 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[0]; 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 = [0] * 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