Posts /

5 mins read ●
06 Sep 2017

# Pigeonhole Sort

As the name implies, this algorithm uses the Pigeonhole Principle to sort items. Although this algorithm is not practically preffered, it strongly demonstrates the wonders of maths.

Pigeonhole Principle
In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. Wikipedia

The strange thing about Pigeonhole Sort is that its performace not only depends on the input size (normal for all other algorithms), but on the input range as well. This means that Pigeonhole Sort will face a hard time sorting data that is spread over a large range. The average performance with respect to time is `O(n + r)`, where `n` is the input size and `r` is the range of input i.e., `max - min`.

## Working

The algorithms starts with `r + 1` empty holes, and then continues to populate them. Holes are numbered such that the minimum value will be in hole `0` while the largest one will be placed in hole `r`. Each hole is marked with the number of items it contains which shows how many times a specific value is repeated. The algorithm then contines by placing the values in correct order based on their hole number.

### Example

Consider a list: `[1, 6, 9, 5, 4, 6]`
We have:
n = 6
r = `9 - 1` = 8
Hence, we have 9 empty holes, or say holes = `[0, 0, 0, 0, 0, 0, 0, 0, 0]`

The algorithm will now iterate over all the values and mark the index `x - min` of the list `holes`, where `x` is a value from list and `min` is the smallest value.

For Example
If x = 6, we’ll have 2 at index 5 in holes i.e., `[_, _, _, _, _, 2, _, _, _]`. This means that we have 2 6’s in our list.

After iterating over all the items, we have:
Indices: `[0, 1, 2, 3, 4, 5, 6, 7, 8]`
Holes = `[1, 0, 0, 1, 1, 2, 0, 0, 1]`

Now, Pigeonhole Sort will visit each hole, and copy the values there to another list. This list will now be sorted.

Sorted = `[1, 4, 5, 6, 6, 9]`

Note

As you can see a lot of holes are empty, this algorithm requires a lot of space even for a small but widely spread data.

See the animation to understand how it really works.

### Code

I have two methods for implementing Pigeonhole Sort in Python: one is a special case.

#### General

``````def pigeonsort(values):
# size of range of values in the list (ie, number of pigeonholes we need)
_min = min(values)
_max = max(values)
_range = _max - _min + 1

# pigeonholes
'''holes = [0 for i in range(_range)]'''
holes =  * _range

# populate the holes
for x in values:
holes[x - _min] += 1

# new sorted list, putting elements back to save space
i = 0
for count in range(_range):
while holes[count] > 0:
#copy all elements from each hole
holes[count] -= 1
values[i] = count + _min
i += 1
# either
print values
# or
return values
``````

#### Special

This method works iff the list has continuous and not-repeating values.

``````def pigeonsort( values ):
_min = min(values)
_max = max(values)
_range = _max - _min

# holes = [0 for i in range(_range + 1)]
holes =  * _range

# filling holes
for value in values:
holes[ value - _min ] = value

#moving back to original; in order
values = [value for value in holes]

return values
``````

See the result in this IPython Notebook. In case of any errors, open an issue in 100 Algorithms repo OR comment below.