How to implement the pigeonhole sorting algorithm in Python

Pigeonhole sort is a non-comparison sorting algorithm that performs sorting in linear time. This algorithm is utilized to sort the integer values where the array length and the range of elements are close. It creates a pigeonhole for each possible data value and places the data items in their corresponding pigeonhole. Lastly, it collects the data items in ascending order to sort the data.

A practical example of pigeonhole sort could be the cabinets in the post offices where every slot represents ZIP codes or other distinguished keys from where the postman can collect the packages. Whenever a new package arrives, it is placed in its proper slot manually.

How it works

The algorithm works in the following steps:

1. Find the minimum and maximum values in the array. Also, calculate the range of the data as maximum−minimum+1maximum-minimum+1.
2. Create an array of the size of the range and name it pigeonhole.
3. Iterate through each array element and place it in the corresponding pigeonhole.
4. Iterate through each pigeonhole element and place all the elements back into the array.

Play the following slides to visualize the working of the pigeonhole sort:

Pseudocode

Let’s see the pseudocode of this algorithm before implementing it in any programming language.

Code example

Let’s implement the code of pigeonhole sort using Python in the following playground:

Code explanation

Let’s discuss the code below:

• Lines 2–4: We create variables to store the minimum, maximum, and range of elements.
• Line 6: We define a list of lists to store array elements at their corresponding pigeonholes.
• Lines 8–9: We iterate through each array element and place it in their pigeonholes.
• Lines 11–15: We create a variable arr_index to store the index and loop through pigeonhole elements. We use a while loop to push the values of each pigeonhole to the original array in order. Lastly, we increment the arr_index after the transfer of each element.
• Lines 18–19: We create an unsorted array and print the array before sorting.
• Lines 21–22: We call the pigeonhole_sort() function and print the array after sorting.

Complexity

The time and space complexity of the pigeonhole sort algorithm is O(n+k)O(n+k), where nn is the length of the array, and kk is the range of the array elements.

Benefits and limitations

Let’s discuss some benefits and limitations of the Pigeonhole sort.

Benefits

• Pigeonhole sort is a non-comparison-based algorithm, which means it doesn’t compare elements for sorting. This is beneficial where comparisons are costly.

• It is a stable algorithm, which means it maintains the order of equal elements.

• It is a linear time algorithm that performs sorting quickly. It is faster than comparison-based sorting algorithms, i.e., merge sort or quick sort.

Limitations

• Pigeonhole sort requires extra memory space to sort. This could be alarming when the large array size, high data range, or the memory is costly.
• It only works with integer or indexable values. It isn’t easily extendable to other data types.