Bucket Sort has a dream: a dream to one day captain a boat.  

The only child of Bead Sort and Radix Sort, he longs to become a fisherman and own his own business. His mom celebrates this idea, and encourages him to pursue it; his dad, a normally-chill guy, wants him to succeed but thinks that the whole idea is pretty stupid. See, there's a problem with this dream...

Photo by Bruce Warrington / Unsplash

Bucket Sort gets violently seasick any time a boat is in his immediate vicinity. He's never been out on the ocean, much less for days on end, and he barely knows which way a fishing pole goes. He couldn't tell you the difference between bait and tackle. In short, he has no idea what he's dreaming of.

But it is still his dream. One day, with luck, he can make it come true. For a few minutes, anyway.

The Rundown

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

Algorithm

  1. SET UP an array of initially empty "buckets".
  2. SCATTER each object from the unsorted array into their corresponding buckets.
  3. SORT each bucket individually.
  4. GATHER items from each bucket in their correct order.

Visualization

Lucky for us, this is an easy algorithm to visualize. Imagine we have the following array:

{ 41, 7, 18, 3, 11, 23, 45, 15 }

We need to divide these items into buckets based on some sort of identifier. For simplicity, we will create the buckets based on the range of values, ten numbers in each bucket. That results in these buckets:

(Fear my l33t MS Paint skillz!)

We can then "scatter" the numbers into each bucket based on their range. That looks like this:

We now sort the items in each bucket using a different sorting algorithm (our implementation uses Insertion Sort) to result in "sorted buckets":

We then "gather" the items from each bucket in order, which results in the sorted array:

{ 3, 7, 11, 15, 18, 23, 41, 45 }

C# Implementation

class BucketSort
{
    public static List<int> Sort(params int[] x)
    {
        List<int> sortedArray = new List<int>();

        int numOfBuckets = 10;

        //Create buckets
        List<int>[] buckets = new List<int>[numOfBuckets];
        for (int i = 0; i < numOfBuckets; i++)
        {
            buckets[i] = new List<int>();
        }

        //Iterate through the passed array 
        //and add each integer to the appropriate bucket
        for (int i = 0; i < x.Length; i++)
        {
            int bucket = (x[i] / numOfBuckets);
            buckets[bucket].Add(x[i]);
        }

        //Sort each bucket and add it to the result List
        for (int i = 0; i < numOfBuckets; i++)
        {
            List<int> temp = InsertionSort(buckets[i]);
            sortedArray.AddRange(temp);
        }
        return sortedArray;
    }

    //Insertion Sort
    public static List<int> InsertionSort(List<int> input)
    {
        for (int i = 1; i < input.Count; i++)
        {
            //2. Store the current value in a variable
            int currentValue = input[i];
            int pointer = i - 1;

            //3. As long as we are pointing to a valid value in the array...
            while (pointer >= 0)
            {
                //4. If the current value is less 
                //   than the value we are pointing at...
                if (currentValue < input[pointer])
                {
                    //5. Move the pointed-at value up one space, 
                    //   and insert the current value 
                    //   at the pointed-at position.
                    input[pointer + 1] = input[pointer];
                    input[pointer] = currentValue;
                }
                else break;
            }
        }

        return input;
    }
    static void Main(string[] args)
    {
        int[] array = new int[] { 43, 17, 87, 92, 31, 6, 96, 13, 66, 62, 4 };

        Console.WriteLine("Bucket Sort");

        CommonFunctions.PrintInitial(array);

        List<int> sorted = Sort(array);

        CommonFunctions.PrintFinal(sorted);
        Console.ReadLine();
    }
}

Time and Space Complexity

Because Bucket Sort uses another sorting algorithm as its "inner" sort algorithm, the time and space complexities for it are directly influenced by the complexities of that "inner" algorithm. This is why our implementation above uses Insertion Sort, which has been shown to work efficiently on small collections, even more efficiently than Quicksort.

What's more interesting (to me, at least) is the average case of this algorithm: O(n + (n2/k) + k), where n is the number of elements and k is the number of buckets. What this tells us is that as the number of elements increases, the performance of this algorithm gets worse(same as every other sorting algorithm), BUT as the number of buckets increases, the performance improves. This suggests that we should have as many buckets as possible.  

What's to stop us from implementing a bucket sort with exactly one item per bucket? Well, the space complexity, for one. This algorithm has a space complexity of O(n * k), and therefore requires much more space as the number of buckets increases. That said, space is cheap, and the tradeoff might be worth it.

Summary

Bucket Sort is an interesting algorithm, in that it tries to make another algorithm's job easier by first sorting the elements into related collections called "buckets". It's not a terribly useful algorithm for general cases, but when the input is evenly distributed it can perform in efficient time. The boat thing, however, is another issue entirely. His dad hopes poor Bucket Sort can see the truth, someday.

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

Happy Coding!