# What is Pigeonhole Sort

**Pigeonhole sort**is a sorting algorithm that works by distributing elements of an unsorted list into a set of "pigeonholes" or buckets based on their values. For example, if you have a list of numbers from 1 to 10, you would create 10 pigeonholes, one for each number.

Then you would iterate through the unsorted list of numbers and place each number into its corresponding pigeonhole based on its value. So, if the number is 5, you would place it in the fifth pigeonhole.

Once all the numbers have been placed into their respective pigeonholes, you would then iterate through the pigeonholes in order and concatenate the elements back into a sorted list.

One important thing to note is that Pigeonhole sort works best when the range of values in the list is small compared to the number of elements in the list. If the range of values is too large, it can become inefficient.

## Who invented it?

The exact origins of Pigeonhole sort are unclear, as it is a very old algorithm that has been known for centuries. However, it was formally described and analyzed in computer science literature by A. J. Lotka in 1926, and later independently rediscovered by John Knuth in the 1960s.

The algorithm gets its name from the concept of "pigeonholes", which refers to the idea that if you have more pigeons than pigeonholes, at least one of the pigeonholes must contain more than one pigeon. This idea is similar to how the algorithm works, as it distributes elements into pigeonholes based on their values and relies on the fact that if there are more elements than pigeonholes, at least one pigeonhole must contain more than one element.

## Pseudocode

```
Pigeonhole_Sort(a[])
Find the minimum and maximum values in the array a[]
Let range = max - min + 1
Create an array of empty "pigeonholes" with size = range
Loop through the array a[] and place each element in the corresponding pigeonhole
for i = 0 to length(a) - 1
hole = a[i] - min
increment pigeonhole[hole]
Loop through the pigeonholes and concatenate the elements back into a sorted list
for i = 0 to range - 1
while pigeonhole[i] > 0
add min + i to the sorted list
decrement pigeonhole[i]
return sorted list
```

In this pseudocode, a[] represents the input array to be sorted, min and max are the minimum and maximum values in the array, range is the size of the range of values in the array, and pigeonhole[] is an array of empty "pigeonholes" with size range. The algorithm works by iterating through the input array, placing each element into its corresponding pigeonhole based on its value, and then concatenating the elements back into a sorted list by iterating through the pigeonholes in order.

## Sample Code

```
// C++ code snippet
vector
``` PigeonholeSort(vector& arr) {
// Find the minimum and maximum values in the array
int min_val = arr[0], max_val = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] < min_val) {
min_val = arr[i];
}
if (arr[i] > max_val) {
max_val = arr[i];
}
}
// Let range = max - min + 1
int range = max_val - min_val + 1;
// Create an array of empty "pigeonholes" with size = range
vector pigeonholes(range, 0);
// Loop through the array and place each element in the corresponding pigeonhole
for (int i = 0; i < arr.size(); i++) {
int hole = arr[i] - min_val;
pigeonholes[hole]++;
}
// Loop through the pigeonholes and concatenate the elements back into a sorted list
vector sorted_arr(arr.size());
int index = 0;
for (int i = 0; i < range; i++) {
while (pigeonholes[i] > 0) {
sorted_arr[index] = i + min_val;
pigeonholes[i]--;
index++;
}
}
return sorted_arr;
}
int main() {
// Example usage
vector arr = {8, 3, 5, 2, 9, 1, 4, 6, 7};
vector sorted_arr = PigeonholeSort(arr);
// Print the sorted array
for (int i = 0; i < sorted_arr.size(); i++) {
cout << sorted_arr[i] << " ";
}
cout << endl;
return 0;
}

```
# Python code snippet
def pigeonhole_sort(arr):
# Find the minimum and maximum values in the array
min_val, max_val = min(arr), max(arr)
# Let range = max - min + 1
range_ = max_val - min_val + 1
# Create an array of empty "pigeonholes" with size = range
pigeonholes = [0] * range_
# Loop through the array and place each element in the corresponding pigeonhole
for i in arr:
hole = i - min_val
pigeonholes[hole] += 1
# Loop through the pigeonholes and concatenate the elements back into a sorted list
sorted_arr = []
for i in range(range_):
while pigeonholes[i] > 0:
sorted_arr.append(i + min_val)
pigeonholes[i] -= 1
return sorted_arr
# Example usage
arr = [8, 3, 5, 2, 9, 1, 4, 6, 7]
sorted_arr = pigeonhole_sort(arr)
print(sorted_arr)
```

```
import java.util.ArrayList;
import java.util.List;
public class PigeonholeSort {
public static List
``` pigeonholeSort(List arr) {
// Find the minimum and maximum values in the array
int minVal = arr.get(0), maxVal = arr.get(0);
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i) < minVal) {
minVal = arr.get(i);
}
if (arr.get(i) > maxVal) {
maxVal = arr.get(i);
}
}
// Let range = max - min + 1
int range = maxVal - minVal + 1;
// Create an array of empty "pigeonholes" with size = range
int[] pigeonholes = new int[range];
// Loop through the array and place each element in the corresponding pigeonhole
for (int i = 0; i < arr.size(); i++) {
int hole = arr.get(i) - minVal;
pigeonholes[hole]++;
}
// Loop through the pigeonholes and concatenate the elements back into a sorted list
List sortedArr = new ArrayList(arr.size());
for (int i = 0; i < range; i++) {
while (pigeonholes[i] > 0) {
sortedArr.add(i + minVal);
pigeonholes[i]--;
}
}
return sortedArr;
}
public static void main(String[] args) {
// Example usage
List arr = List.of(8, 3, 5, 2, 9, 1, 4, 6, 7);
List sortedArr = pigeonholeSort(arr);
// Print the sorted array
System.out.println(sortedArr);
}
}

## Time and Space Complexity

- Time complexity: O(n + range), where n is the number of elements in the array and range is the difference between the maximum and minimum values in the array. In the worst case, when the range is much larger than n, the time complexity can be closer to O(range).

- Space complexity: O(range), as we need to create an array of size range to store the pigeonholes.

Note that the time and space complexity of Pigeonhole Sort depends heavily on the range of values in the input array. If the range is small, then Pigeonhole Sort can be much faster than other sorting algorithms, as it avoids many of the comparisons that other sorting algorithms make. However, if the range is very large, then Pigeonhole Sort may not be practical, as it requires a large amount of memory to store the pigeonholes.

## Advantages

- Pigeonhole Sort is very easy to understand and implement, requiring only a few lines of code.
- Pigeonhole Sort is very efficient when the range of values in the input array is small, as it avoids many of the comparisons that other sorting algorithms make.
- Pigeonhole Sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input array.

## Disadvantages

- Pigeonhole Sort has a time complexity of O(n + range), which can be slow if the range is much larger than the number of elements in the input array.
- Pigeonhole Sort requires a large amount of memory to store the pigeonholes, which can be a problem if the range is very large.
- Pigeonhole Sort is not an in-place sorting algorithm, meaning that it requires additional memory to store the sorted array.
- Overall, Pigeonhole Sort is a useful sorting algorithm when the range of values in the input array is small and memory is not a concern. However, for larger input arrays or very large ranges of values, other sorting algorithms may be more practical.