Pigeonhole Sort

Pigeonhole sort is an interesting sorting algorithm that makes use of an array filled with zeros and its indices. It can sort values in linear time and is relatively simple to implement. However, the tradeoff for its sorting speed is the space that it requires. Also, since it makes use of array indices, only positive integers can be sorted using this algorithm.

So the basic idea of pigeonhole sort is:

  • Create a new array (let’s call it pigeonholeArray) and fill it with zeros.
  • Iterate through the unsorted user’s array (inputArray).
  • For each value of the inputArray, add 1 to the index corresponding with the value in the pigeonholeArray.

Let’s say for this example, we want to sort this inputArray:

The first thing the algorithm needs to know is what the maximum value of the inputArray is. We need to create a pigeonholeArray that has indices that go up to the max value. If we don’t know the maximum, we’ll have to loop through the inputArray one time to figure it out. In this case, our biggest value is 7, thus we need to create a pigeonholeArray that can hold 8 elements (which will have indices 0 to 7).

Now we need to loop through the unsorted inputArray (again), and as we do that, we will add 1 to the pigeonholeArray’s value at the pigeonholeArray’s index corresponding with the inputArray’s value. So as we iterate our input array, our pigeonhole array will look like this:

As you can see, after looping through the entire inputArray, our pigeonholeArray will contain all of inputArray’s values. We will just have to make one last iteration through the pigeonholeArray. For each pigeonholeArray’s value that is greater than zero, we’ll add the pigeonholeArray’s index to the inputArray. We can replace the old values in the inputArray so that no new array needs to be created.

Check out the completed algorithm below: