BucketSort - generalized form of a counting sort.

bucket_sort.js

// Assume you are sorting floating point values.
// [0.33, 0.22, 0.4, 0.1, 0.0] => [0.0, 0.1, 0.22, 0.33, 0.4]
function _hash(value) {
  return Math.floor(value / 0.1); // create buckets with sized 0.1
}

function _createBucket(array) {
  var buckets = {}; // A hash that has keys that represent a range of values.

  for (var i = 0; i < array.length; i++) {
    var k = _hash(array[i]); // Figure out what bucket this value belongs to.
    buckets[k] = (buckets[k] || []).concat(array[i]); // add to bucket which is an array
  }

  return buckets;
}

function _insert(array, position, value) {
  var previousIndex = position - 1;

  while((previousIndex >= 0) && (array[previousIndex] > value)) {
    array[previousIndex + 1] = array[previousIndex];
    previousIndex--;
  }

  array[previousIndex + 1] = value;
}

function _insertionSort(array) {
  for (var i = 0; i < array.length; i++) {
    _insert(array, i, array[i]);
  }
}

function _extract(buckets, array) {
  var position = 0;

  for (var i = 0; i < array.length; i++) {
    var bucket = buckets[i];  // Pick the next bucket from the ordered hash of buckets
    _insertionSort(bucket);   // Sort bucket's values (array).
    for (var k = 0; k < bucket.length; k++) {
      array[position++] = bucket[k]; // extract values from bucket and use them to replace array value.
    }
  }
}

function bucketSort(array) {
  // The following conditions must be met in order for it to be a bucket sort:
  // 1. uniformed disturbtion - n buckets are created to even parition
  // the input range.
  // 2. the buckets must be ordered.
  // It peforms in O(n) but if the buckets are not uniformly disturbted, it
  // reduces itself to a insertion sort which is O(n^2)
  // NOTE: this is a more generalized form of the counting sort, where there was
  // only one discrete key for a bucket, unlike bucket sort which accepts a range
  var buckets = _createBucket(array);
  _extract(buckets, array);
}