Implement Bucket Sort in JavaScript

JavaScript
October 2, 2016

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 bucketSort function (array, bucket size) 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.

// InsertionSort to be used within bucket sort function insertionSort(array) { var length = array.length; for(var i = 1; i < length; i++) { var temp = array[i]; for(var j = i - 1; j >= 0 && array[j] > temp; j--) { array[j+1] = array[j]; } array[j+1] = temp; } return array; } // Implement bucket sort function bucketSort(array, bucketSize) { if (array.length === 0) { return array; } // Declaring vars var i, minValue = array[0], maxValue = array[0], bucketSize = bucketSize || 5; // Setting min and max values array.forEach(function (currentVal) { if (currentVal < minValue) { minValue = currentVal; } else if (currentVal > maxValue) { maxValue = currentVal; } }) // Initializing buckets var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var allBuckets = new Array(bucketCount); for (i = 0; i < allBuckets.length; i++) { allBuckets[i] = []; } // Pushing values to buckets array.forEach(function (currentVal) { allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal); }); // Sorting buckets array.length = 0; allBuckets.forEach(function(bucket) { insertionSort(bucket); bucket.forEach(function (element) { array.push(element) }); }); return array; }

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!

More Blog Posts