-
-
Save jonataswalker/55db90e6174451c5ffd591c5260590e5 to your computer and use it in GitHub Desktop.
Fast Bucket Sort for Integers in JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment