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...

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.

**Created By:**Unknown**Type:**Distribution**Stable?**Yes**Average-Case:***O(n + (n*^{2}/k) + k)**Worst-Case:***O(n*^{2})**Space Complexity:***O(n * k)***Sample Project:**Over on GitHub

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

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:

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 }

```
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();
}
}
```

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 + (n ^{2}/k) + k)*, where

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.

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!

]]>Radix Sort is possibly the chillest person you will ever meet.

The third child of the family patriarchs Selection and Merge Sorts, he greets every problem, every family squabble, every thing that ever happens to him with "Cool, man". He once witnessed a car crash and later described the event as "two cars having a meeting of the minds" (the family hasn't let him live this down). A peculiar scent seems to pervade areas he inhabits. He's the most easy-going person at the reunion.

At least, that's what he wants you to think.

In reality, at this moment, he's terrified. Terrified that someone will find out that he's a fraud. That job as an auto mechanic the family still thinks he has? He was fired last week over something stupid. Only his beloved wife Bead Sort knows, and he is petrified that someone else will discover his secret. With no way to provide for his family, he feels like a failure. Beady tried to help, tried to make him feel like he contributes, but he seems to only shrink further away from her.

He's holding his breath, praying no one finds out, barely clinging to his friendly, chill facade.

**Created By:**Unknown, possibly Herman Hollerith (1887)**Type:**Distribution**Stable?**Depends on implementation**Worst-Case:***O(w * n)***Space Complexity:***O(w + n)***Sample Project:**Over on GitHub

- SORT the numbers into buckets based on the value of the least-significant digit.
- SORT the numbers in each bucket again, based on the value of the next-least-significant digit.
- CONTINUE UNTIL there are no significant digits left.

Suppose we have the following array:

{ 5419, 13, 384, 201, 7, 2232, 3, 81, 19, 4029 }

Radix Sort's algorithm tells us we need to sort on the least-signification digit. We should therefore sort based on these values:

{9, 3, 4, 1, 7, 2, 3, 1, 9, 9}

Doing that sort results in this intermediate array:

{ 201, 81, 2232, 13, 3, 384, 7, 5419, 19, 4029 }

We now need to sort on the second-least-significant digit. Problem is, some of these numbers (e.g. 3 and 7) don't have such a digit. We therefore need to impose a digit at that position of 0.

{ 201, 81, 2232, 13, 03, 384, 07, 5419, 19, 4029 }

We can now sort based on the second-least-significant digit, resulting in:

{ 201, 03, 07, 13, 19, 5419, 4029, 2232, 81, 384 }

We need to do this twice more; once for the third-least-significant digit:

{ 3, 7, 13, 19, 4029, 81, 201, 2232, 384, 5419 }

And, finally, we sort based on the most-significant digit, resulting in the final sorted array:

{ 3, 7, 13, 19, 81, 201, 384, 2232, 4029, 5419 }

What we have just done is technically called a least-significant digit radix sort.

The audibilization of this sort is pretty neat, check it out:

```
class RadixSort
{
public static void Main()
{
int[] array = { 330, 8, 27, 4419, 55, 816, 419, 77, 622, 1234, 6, 9, 241, 1, 35, 7733, 4, 69 };
int length = array.Length;
Console.WriteLine("Radix Sort");
CommonFunctions.PrintInitial(array);
int max = array.Max();
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSort(array, length, exp);
}
CommonFunctions.PrintFinal(array);
Console.ReadLine();
}
//This is a modified version of Counting Sort from an earlier post
//We need to do Counting Sort against each group of integers,
//where the groups are made based on the position of significant digits.
//So, we use Counting Sort on the least-significant digit, then the next-least, etc.
//After that, we concatenate the groups together to form the final array.
public static void CountingSort(int[] array, int length, int exponent)
{
//Create a new "output" array
int[] output = new int[length]; // output array
int i;
//Create a new "counting" array which stores the count of each unique number
int[] count = new int[10];
for (i = 0; i < 10; i++)
{
count[i] = 0;
}
for (i = 0; i < length; i++)
{
count[(array[i] / exponent) % 10]++;
}
//Change count[i] so that count[i] now contains actual position of
//this character in the output array.
for (i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
//Build the output array.
//This is the tricky part.
for (i = length - 1; i >= 0; i--)
{
output[count[(array[i] / exponent) % 10] - 1] = array[i];
count[(array[i] / exponent) % 10]--;
}
//Copy the output array to the final array.
for (i = 0; i < length; i++)
{
array[i] = output[i];
}
}
}
```

This algorithm has a unique worst-case time complexity: *O(w * n)*, where *w* is the number of bits required to store each value. This makes intuitive sense; it means that as the number of significant digits grows, the time needed for the algorithm to complete also grows.

The space complexity for this algorithm is even more obvious: *O(w + n)*, which means that the space required is a direct function of the number of digits needing to be sorted.

Both of these values are relatively low compared to other sorting algorithms. Because of this, Radix Sort is a pretty useful real-world algorithm. In fact, because Radix Sort doesn't actually need the values being sorted to be integers, we can use this algorithm to sort various things, including letters and words.

Radix Sort is one of the more useful real-world sorts; because it operates on least-significant digit, it can be used to sort quite a lot more than just numbers. But be aware; beneath the chill, "whatever, man" surface, he's quietly petrified that someone he cares about is going to discover his secret.

The final member of the family, Bucket Sort, is our last entry in this series, and he really wishes he could own a boat. There's just one problem with that.

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

Happy Coding!

]]>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.

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.

**Created By:**Unknown**Type:**Distribution**Stable?**Yes**Worst-Case:***O(n + k)***Space Complexity:***O(n + k)***Sample Project:**Over on GitHub

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

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:

a_{1} |
a_{2} |
a_{3} |
a_{4} |
a_{5} |
a_{6} |
a_{7} |
a_{8} |
---|---|---|---|---|---|---|---|

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:

a_{1} |
a_{2} |
a_{3} |
a_{4} |
a_{5} |
a_{6} |
a_{7} |
a_{8} |
---|---|---|---|---|---|---|---|

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 }

```
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();
}
}
```

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.

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.

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

Happy Coding!

]]>Counting Sort is the star athlete of the family, even more so than Comb Sort.

A soccer striker with a knack for faking out the keeper, she scores goals like football linebackers down calories. She's been playing since she could walk; soccer is all she wants to do. She's even got a potential scholarship lined up to go play for the big state college next year, something she's eagerly looking forward to once she graduates.

That is, *if* she graduates. Her grades have not been, well, *good*. The high school has so far looked the other way because she helps the team win so much, but that won't fly in college. All she has to do is get a B or better average for her senior year, so she has enlisted a team of people to help her study: her dad Cocktail Shaker Sort, doting but gruff grand-uncle Bitonic Merge Sort, history-teacher uncle Pigeonhole Sort, and first cousin Comb Sort (who has a similar problem). They are hoping, trying, to ensure that Counting Sort can go to college and play.

But time is running out, and it's starting to look like they're gonna need a miracle for Counting Sort to live her dream.

**Created By:**Harold H Seward (1954)**Type:**Distribution**Stable?**Yes**Worst-Case:***O(n + k)***Space Complexity:***O(n + k)***Sample Project:**Over on GitHub

- COUNT how many times a particular value appears, and store those values in a "count" array.
- CREATE an "order" array which shows in what order the values should appear.
- SORT the main array using the order and count arrays.

This sort works by counting how many instances of a particular number show up. The algorithm above is not very descriptive, so let's see if we can make a more meaningful example.

Say we have the following starter array:

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

Counting sort would create a new "count" array of size *k* (which we will define to be 10 for simplicity) and store the number of times a given value appears.

That array would look like this:

a_{1} |
a_{2} |
a_{3} |
a_{4} |
a_{5} |
a_{6} |
a_{7} |
a_{8} |
a_{9} |
a_{10} |
---|---|---|---|---|---|---|---|---|---|

1 | 2 | 0 | 1 | 3 | 0 | 0 | 1 | 0 | 0 |

We read this as "the value 1 appears 1 time, the value 2 appears 2 times, the value 3 appears 0 times" and so on.

We then need to create a "order" array in which the value increases, to show the order of the elements.

a_{1} |
a_{2} |
a_{3} |
a_{4} |
a_{5} |
a_{6} |
a_{7} |
a_{8} |
a_{9} |
a_{10} |
---|---|---|---|---|---|---|---|---|---|

1 | 2 | 2 | 4 | 5 | 5 | 5 | 8 | 8 | 8 |

Using the counting array and the order array, we can place the values in their correct order:

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

In researching this algorithm I found it particularly helpful to step through each for loop of this implementation, to see what each array had as its values.

```
class CountingSort
{
static void Sort(int[] array)
{
int length = array.Length;
//Create a new "output" array
int[] output = new int[length];
//Create a new "counting" array
//which stores the count of each unique number
int[] count = new int[100];
for (int i = 0; i < 100; ++i)
{
count[i] = 0;
}
for (int i = 0; i < length; ++i)
{
++count[array[i]];
}
//Change count[i] so that count[i] now contains the
//actual position of this character in the output array.
for (int i = 1; i <= 99; ++i)
{
count[i] += count[i - 1];
}
//Build the output array.
//To make this sorting algorithm stable,
//we are operating in reverse order.
for (int i = length - 1; i >= 0; i--)
{
output[count[array[i]] - 1] = array[i];
--count[array[i]];
}
//Copy the output array to the final array.
for (int i = 0; i < length; ++i)
{
array[i] = output[i];
}
}
public static void Main()
{
int[] array = { 64, 11, 83, 8, 13, 45, 92, 98, 55, 17, 41, 81, 11, 64, 14, 41, 11, 92 };
Console.WriteLine("Counting Sort");
CommonFunctions.PrintInitial(array);
Sort(array);
CommonFunctions.PrintFinal(array);
Console.ReadLine();
}
}
```

Counting Sort can be fairly efficient: it's worst-case time complexity is *O(n + k)*, where *k* is the range of potential values. For small values of *k*, this is an efficient time. The problem happens when *k* is large; in those scenarios, this algorithm becomes markedly less efficient than other distribution algorithms (e.g. Radix Sort).

Because the algorithm needs to create a "count" array that is the same size as the range of possible values *k*, the space complexity is also *O(n + k)*. Again, this is not a problem with small *k*, but with large *k* you could start running into memory or space issues.

Counting Sort is an efficient sorting algorithm for small ranges of potential values *k*. However, once the range becomes large, Counting Sort quickly becomes overshadowed by other, more efficient sorts. With a little help from her grand-uncle and her cousin, she might, just might, make it to college. She hopes.

The military-veteran uncle, Bitonic Merge Sort, is next, and if you peel back his gruff exterior you might find he's a bit of a softy.

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

Happy Coding!

]]>