Editing Pigeonhole sort (section)

==Example==
Suppose one were sorting these value pairs by their first element:

* (5, "hello")
* (3, "pie")
* (8, "apple")
* (5, "king")

For each value between 3 and 8 we set up a pigeonhole, then move each element to its pigeonhole:

* 3: (3, "pie")
* 4:
* 5: (5, "hello"), (5, "king")
* 6:
* 7:
* 8: (8, "apple")

The pigeonhole array is then iterated over in order, and the elements are moved back to the original list.

The difference between pigeonhole sort and counting sort is that in counting sort, the auxiliary array does not contain lists of input elements, only counts:

* 3: 1
* 4: 0
* 5: 2
* 6: 0
* 7: 0
* 8: 1

For arrays where ''N'' is much larger than ''n'', [[bucket sort]] is a generalization that is more efficient in space and time.