Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the length of the range of possible key values are approximately the same.

### How It Works

- Find the minimum and maximum values in array. Let the minimum and maximum values be ‘min’ and ‘max’ respectively. Also find range as max-min+1.
- Set up an array of initially empty “pigeonholes” the same size as of the range calculated above.
- Visit each element of the array and then put each element in its pigeonhole. An element arr[i] is put in hole at index arr[i] – min.
- Start the loop all over the pigeonhole array in order and put the elements from non- empty holes back into the original array.

### Example

def pigeonhole_sort(a): # size of range of values in the list my_minimum = min(a) my_maximum = max(a) size = my_maximum - my_minimum + 1 # our list of pigeonholes holes = [0] * size # Populate the pigeonholes. for x in a: assert type(x) is int, "integers only please" holes[x - my_minimum] += 1 # Put the elements back into the array in order. i = 0 for count in range(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + my_minimum i += 1 a = [8, 3, 2, 5, 4, 6, 4, 8] print("Sorted order is : ", end =" ") pigeonhole_sort(a) for i in range(0, len(a)): print(a[i], end =" ")

Run this and you will see this

>>> %Run pigeonhole_sort.py Sorted order is : 2 3 4 4 5 6 8 8

### Link

https://github.com/programmershelp/maxpython/blob/main/code%20example/pigeonhole_sort.py