Editing Pigeonhole sort (section)

{{Short description|Sorting algorithm}}
__NOTOC__
{{refimprove|date=July 2017}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|data=[[Array data structure|Array]]
|time=<math>O(N+n)</math>, where ''N'' is the range of key values and ''n'' is the input size 
|space=<math>O(N+n)</math>
|optimal=If and only if <math>N=O(n)</math>
}}
'''Pigeonhole sorting''' is a [[sorting algorithm]] that is suitable for sorting lists of elements where the number ''n'' of elements and the length ''N'' of the range of possible key values are approximately the same.<ref>{{cite web| url = https://xlinux.nist.gov/dads/HTML/pigeonholeSort.html| title = NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort}}</ref> It requires [[big O notation|O]](''n'' + ''N'') time.  It is similar to [[counting sort]], but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there."<ref>{{cite web|last1=Black|first1=Paul E.|title=Dictionary of Algorithms and Data Structures|url=https://xlinux.nist.gov/dads/HTML/pigeonholeSort.html|website=NIST|access-date=6 November 2015}}</ref>

The pigeonhole algorithm works as follows:
#  Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes" (analogous to a [[pigeon-hole messagebox]] in an office or desk), one pigeonhole for each key in the [[Range_(computer_science)|range]] of the keys in the original array.
#  Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key.
#  Iterate over the pigeonhole array in increasing order of keys, and for each pigeonhole, put its elements into the original array in increasing order.