Pigeonhole sorting, also known as count sort (not to be confused with counting sort

Counting sort

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to...

), is a sorting algorithm

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...

 that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same. It requires O

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

(n + N) time.

The pigeonhole algorithm works as follows:

1. Given an array of values to be sorted, set up an auxiliary array of initially empty "pigeonholes," one pigeonhole for each key through the range
   Range (computer science)
   In computer science, the term range may refer to one of three things:# The possible values that may be stored in a variable.# The upper and lower bounds of an array.# An alternative to iterator.-Range of a variable:...
   
    of the original array.
2. 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.
3. Iterate over the pigeonhole array in order, and put elements from non-empty pigeonholes back into the original array.

For example, suppose we 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")

We then iterate over the pigeonhole array in order and move them 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

Using this information we can perform a series of exchanges on the input array that puts it in order, moving items only once. Pigeonhole sort, in contrast, moves items twice: once onto the pigeonhole/bucket array and again onto the destination array.

For arrays where N is much larger than n, bucket sort

Bucket sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of...

is a generalization that is more efficient in space and time.