Skip to content

Instantly share code, notes, and snippets.

@dankogai
Created January 10, 2012 21:55
Show Gist options
  • Save dankogai/1591439 to your computer and use it in GitHub Desktop.
Save dankogai/1591439 to your computer and use it in GitHub Desktop.
General-purpose bucket sort in JS
bucketSort = function(src, k2i, v2k) {
if (src.length <= 1) return src;
k2i = k2i || function(k, d){ return (''+k).charCodeAt(d) || 0 };
v2k = v2k || function(v){ return v };
/* first we bundle elements with same keys */
var valOf = Object.create(null), concat = Array.prototype.concat;
src.forEach(function(v){
var k = v2k(v);
if (valOf[k]) valOf[k].push(v);
else valOf[k] = [v];
});
return concat.apply([],
/* then we sort its keys ... */
(function inner(src, depth){
var buckets = [];
/* spread the items into buckets */
src.forEach(function(v) {
var i = k2i(v, depth, src);
if (buckets[i]) buckets[i].push(v);
else buckets[i] = [v];
});
return concat.apply([], buckets
.filter(function(v){ return !!v }) /* no empty buckets */
.map(function(v) {
return v.length === 1
? v
: inner(v, depth+1) /* recurse if necessary */
})
);
})(Object.keys(valOf), 0)
/* … and retrieve the values */
.map(function(k){ return valOf[k]})
);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment