The youngest child of the family patriarchs, Pigeonhole Sort could get away with murder, at least as far as his siblings are concerned.  

Their mother dotes on "her little boy" despite that fact that he's a full-grown adult. She does his laundry, helps with his chores, and generally cleans up after him. His siblings think this is ridiculous, but he doesn't mind. He likes the attention.

This might explain why he has shown up to each of the last four reunions with a different girlfriend.

Photo by Dan Gold / Unsplash

But despite his preference for new people, he also likes giving attention. A history teacher at the local middle school, Pigeonhole Sort loves kids but will probably never have them, and so he spends a lot of his time doting on his nieces and nephews. One of them, Counting Sort, has recently asked him to help her study to try to earn a scholarship to the big state school. He's flattered, because he wasn't the best student either. But for his beloved niece, he'll do anything, even if that means studying trigonometry for the first time in ten years.

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound

Algorithm

  1. DETERMINE the range of possible values from the max and min values in the collection.
  2. CREATE a set of "pigeonholes", one for each value in the range.
  3. FOR EACH value in the unsorted array, mark how many times that value appears by incrementing the value in the pigeonhole.
  4. COPY each non-zero value from the pigeonholes into the new sorted array.

Visualization

Pigeonhole Sort is very similar to Counting Sort, so let's use the sample unsorted array from that post:

{ 5, 2, 5, 8, 1, 2, 4, 5 }

We can see that our range of possible values is 1 to 8, so we create a "pigeonhole" array that looks like this:

a1 a2 a3 a4 a5 a6 a7 a8
0 0 0 0 0 0 0 0

Now we loop through the unsorted array, and for each value found we increment the value in the corresponding pigeonhole.  That results in this:

a1 a2 a3 a4 a5 a6 a7 a8
1 2 0 1 3 0 0 1

From this, we can see that value 1 appears once, value 2 appears twice, value 5 appears 3 times, and so on. We can therefore use this pigeonhole array to create the final, sorted array:

{ 1, 2, 2, 4, 5, 5, 5, 8 }

C# Implementation

class PigeonholeSort
{
    public static void Sort(int[] array)
    {
        int length = array.Length;

        //Find the range of values in the array
        int min = array.Min();
        int max = array.Max();
        int range = max - min + 1;

        //Create a set of pigeonholes with the size of the range of values
        int[] pigeonholes = new int[range];
        for (int i = 0; i < length; i++)
        {
            pigeonholes[i] = 0;
        }

        //For each value in the array, 
        //mark how many times the index of the pigeonhole 
        //appeared in the root array.
        for (int i = 0; i < length; i++)
        {
            pigeonholes[array[i] - min]++;
        }

        int index = 0;

        //Use the pigeonhole array to sort the main array.
        for (int j = 0; j < range; j++)
        {
            //We are using a post-decrement here 
            //to keep track of the number of values 
            //we've already added to the array.
            while (pigeonholes[j]-- > 0)
            {
                array[index] = j + min;
                index++;
            }
        }

    }

    static void Main()
    {
        int[] array = {51, 18, 99, 23, 40, 1, 82, 85, 18, 12, 76};

        CommonFunctions.PrintInitial(array);

        Sort(array);

        CommonFunctions.PrintFinal(array);

        Console.ReadLine();
    }
}

Time and Space Complexity

As mentioned earlier, Pigeonhole Sort is remarkably similar to Counting Sort, which is probably why they get along so well. Their worst-case time complexities match: both are O(n + k).

As with Counting Sort, Pigeonhole Sort works best when k is small, and becomes rather inefficient as k gets larger. We can therefore say that Pigeonhole Sort may be useful in certain scenarios, but we are probably better off going with a different algorithm for real production code.

Summary

Pigeonhole Sort works well on small collections, but its efficiency begins to wane as the size of the collection increases. For real production apps, it's utility is limited. That said, he will do anything for his niece, even if that means sitting up, late at night, trying to memorize the difference between isosceles and scalene triangles.

The green thumb of the family, Gnome Sort, is next, and she just wants to fit in.

Gnome Sort in C#
Gnome Sort is brand new to the family. The girlfriend of Pigeonhole Sort and a hopeless romantic, she is eager to meethis parents and siblings and make good impressions on them. She can’t wait fora chance to show off the bounty of her vegetable garden, and has brought squash,carrots, and fresh …
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!