Pigeonhole sorting takes linear time, which is the best possible performance for sorting since one has to look at all of the objects to be sorted. However, it requires
- that no two objects in the array be identical;
- an invertible function mapping the objects you are sorting to integers within a fixed range (say, 0 to 1000). (If you're sorting integers, just take them as they come.)
The algorithm works as follows.
- Set up an array of initially empty "pigeonholes" the size of the range.
- Go over the original array, putting each object in its pigeonhole.
- 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 size of the pigeonhole array. If it is too big, steps 1 and 3 will significantly slow down the algorithm.
someone provide (pseudo)code?