C# Faster Bucket Sort
Bucket Sort
In a previous article, we explored the general concept of Bucket Sort. Turns out Bucket Sort can be made faster.
All it takes is some basic consideration for the way C#.NET works.
Memory Allocation
The general outline of the bucket sort algorithm tells us that we need to create an array of buckets to store values. Then after all elements have been stored, each bucket is emptied in order and the list is magically sorted.
In practice this is costly because some buckets might go completely unused. In the Bucket Sort article we initialized every bucket before adding elements. You do not need to be a C# expert to understand that memory must be set aside for each class that is initialized. Setting aside memory (memory allocation) takes time.
Thus we can shave off a considerable amount of time from the Bucket Sort algorithm by intializing buckets only when we need them. (How to do that? When adding elements, first check if the bucket is null, initialize if it is).
The second speed improvment comes from choosing the right type of class for the bucket. In the previous article we used the List<> class because it has the Add command which is simple to understand. However, under the hood, when a single element is added to a List<> class, the internal array is expanded to 4 cells. (Basically when the internal array of a List<> is full, all the elements are copied over to a new array double the size of the original array).
For the purpose of bucket sort, it would be more efficient to have a list that does not constantly copy elements between arrays and does not use any extra space. Turns out the LinkedList<> class is perfect for this. The only difference with LinkedList is using an AddLast call instead of Add, (AddLast is used instead of AddFirst to keep the sorting algorithm stable, ie. keep equal elements in the same order). Also the iteration is a little different, look at the source code to get what I mean. It's not too difficult.
Faster Bucket Sort
The first improvement to the bucket sort algorithm, which was initializing buckets only when they are needed makes the algorithm a lot faster.
The second improvement, which was using LinkedList instead of List gives only a slight improvement in speed, but an improvment nonetheless.
Finally remember that Bucket Sort works based on an array of buckets. Meaning that the bucket sort algorithm is fastest when the range of values being sorted is small (since the array of buckets will be small).