Fast Bucket Sort for Integers in JS

bsort.js

// Copyright 2011, Tom Switzer
// Under terms of ISC License: http://www.isc.org/software/license

/**
 * Sorts an array of integers in linear time using bucket sort.
 * This gives a good speed up vs. built-in sort in new JS engines
 * (eg. V8). If a key function is given, then the result of
 * key(a[i]) is used as the integer value to sort on instead a[i].
 *
 * @param a A JavaScript array.
 * @param key A function that maps values of a to integers.
 * @return The array a.
 */
function bsort(a, key) {
    key = key || function(x) { return x };
    var len = a.length,
        buckets = [],
        i, j, b, d = 0;
    for (; d < 32; d += 4) {
        for (i = 16; i--;)
            buckets[i] = [];
        for (i = len; i--;)
            buckets[(key(a[i]) >> d) & 15].push(a[i]);
        for (b = 0; b < 16; b++)
            for (j = buckets[b].length; j--;)
                a[++i] = buckets[b][j];
    }
    return a;
}

This is indeed fast:

var len = 1e6;
var min = 0;
var max = 1e6;

var arr1 = utils.createArray(len, min, max);
var arr2 = utils.createArray(len, min, max);
var arr3 = utils.createArray(len, min, max);

console.time('sortNative');
arr1.sort((a, b) => a - b);
console.timeEnd('sortNative'); // <--------------------------- 393ms

// yours
console.time('bsort');
bsort(arr2);
console.timeEnd('bsort'); // <---------------------------------- 209ms

// from http://stackoverflow.com/a/3817440/4640499
console.time('sortRadix');
sortRadix(arr3);
console.timeEnd('sortRadix'); // <---------------------------- 310ms

Great sharing!!

How this could be deal with negative numbers?

Fast: Yes. Awesome job.
Readable: Nopes

Better variable names may help. High level description of the 4 loops and how their lengths were formulated may help immensely as well. :)

@tixxit