Pigeonhole Sort is a sorting algorithm 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(n + Range) time where n is number of elements in input array and ‘Range’ is number of possible values in array.
Working(Pseudo code) for Pigeonhole Sort:
Pigeonhole sort is similar to counting sort, so here is a comparison between Pigeonhole Sort and counting sort.
Example of Pigeonhole Sort:
O(n + N)