How does the pigeonhole sort algorithm sort elements?

The Pigeonhole Sort algorithm sorts elements by placing each item in a 'pigeonhole' corresponding to its key value.

Pigeonhole Sort is a sorting algorithm that works by creating an array of 'pigeonholes' or 'buckets' for each possible key value in the input. The algorithm then iterates over the input, placing each item in the pigeonhole corresponding to its key value. Once all items have been placed in their respective pigeonholes, the algorithm iterates over the pigeonholes in order, outputting the items found in each one. This results in a sorted list of items.

The first step in the Pigeonhole Sort algorithm is to determine the range of key values in the input. This is done by finding the minimum and maximum key values. The number of pigeonholes needed is then calculated by subtracting the minimum key value from the maximum and adding one. This ensures that there is a pigeonhole for each possible key value.

Next, an array of pigeonholes is created. Each pigeonhole is initially empty. The algorithm then iterates over the input, placing each item in the pigeonhole corresponding to its key value. This is done by subtracting the minimum key value from the key value of the item, which gives the index of the pigeonhole in which the item should be placed.

Once all items have been placed in their respective pigeonholes, the algorithm iterates over the pigeonholes in order. For each pigeonhole, the items found in it are outputted in the order they were placed in the pigeonhole. This results in a sorted list of items.

Pigeonhole Sort is a simple and efficient sorting algorithm when the range of key values is small. However, it can be inefficient when the range of key values is large, as it requires a large amount of memory to create the pigeonholes. Furthermore, it is not suitable for sorting items with non-integer key values, as it relies on using the key values as indices into an array.