Bucket sort is a distribution sort. It works by arranging elements into ‘buckets’ which are then sorted using another sort. This typically utilizes insertion sort then merged into a sorted list.
Bucket sort is exceptionally fast because of the way elements are strategically assigned to buckets. This is normally through using an array where the index is the value. This means that there’s a higher cost of memory for the sake of speed.
Bucket sort is at its best when it can distribute elements evenly throughout the buckets. If values are sparsely allocated, a larger bucket size is more optimal because the values can be separated more evenly. The opposite is also true where a densely allocated array would perform better with a smaller bucket size.
You should normally only use bucket sort when you generally know that elements will be evenly distributed, and when memory usage is not an issue.
Bucket sort performs at its worst, quadratic — O(n²), when all elements are distributed to the same bucket. In this case bucket sort takes on the complexity of the inner sorting algorithms only if a single bucket needs to be sorted.
That being said, a bucket sort could be made to work with large bucket sizes by using insertion sort on small buckets, and merge or quicksort on large buckets.
The time complexity of this algorithm, at worst case, is quadratic — O(n²). The average case, which is likely the case if you have an idea of input size and distribution, is O(n + k).
The space complexity is auxiliary — O(n+k).
A common implementation of bucket sort works by splitting the array of size n into k buckets which holds a specific range of element values. These buckets are then sorted using a sorting algorithm which can be chosen based on the expected input size.
Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.
I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!