Implement Bucket Sort in JavaScript

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. 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;
}