Pigeonhole Sort

This is an example of the non-comparison sorting technique. It is used where the number of items and the range of possible key values is approximately the same.

To perform this sort, we need to make some holes. The number of holes needed is decided by the range of numbers. In each hole, items are inserted. Finally deleted from the hole and stored into an array for sorted order.

Here is the algorithm:

Begin
   find max and min from the array list
   holeRange := max – min +1
   define holeRange number of Lists

   for i := 0 to n-1 do
      hole[array[i]-min].append(array[i])
   done

   count := 0
   for j := 0 to holeRange-1 do
      while hole[j] is not empty do
         array[count] := get first node of hole[j] and delete it
         count := count +1
      done
   done
End

Here is the implementation:

        public static void PigeonHoleSort(int[] arr)

        {

            int max = Enumerable.Max(arr);

            int min = Enumerable.Min(arr);

            int holeRange = max - min + 1;

            int[] pigeonHoles = new int[holeRange];

            for (int i = 0; i < arr.Length; ++i)

            {

                pigeonHoles[arr[i] - min]++;

            }

            int writeIndex = 0;

            for (int i = 0; i < holeRange; ++i)

            {

                while(pigeonHoles[i]-- > 0)

                {

                    arr[writeIndex++] = i + min;

                }

            }

        }

Complexity: Time: O (n + (max - min)), Space: O(max - min)