Implement Bucket Sort in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…

Implement Bucket Sort in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. If you’re new to sorting algorithms, or algorithms in general, read this first to get a solid foundation for moving forward. Today I’ll be covering everything you need to know about bucket sort.

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.

When it’s fast

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.

When it’s slow

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.

Complexity

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

Simplified Pseudocode

Import some type of insertion sort to use in bucket sort function

 Create vars for i, min, max, and bucket size
 Find min and max value
 Create amount of buckets
 Push values to correct buckets 
 Sort buckets

Code

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.

JavaScript eBook

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…