Alex Rivera | Logout

Fastest way to sort 32bit signed integer arrays in JavaScript?

Asked 2011-11-10T16:02:20.253
36
_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/*
RADIX SORT
Use 256 bins
Use shadow array
- Get counts
- Transform counts to pointers
- Sort from LSB - MSB
*/
function radixSort(intArr) {
    var cpy = new Int32Array(intArr.length);
    var c4 = [].concat(_radixSort_0); 
    var c3 = [].concat(_radixSort_0); 
    var c2 = [].concat(_radixSort_0);
    var c1 = [].concat(_radixSort_0); 
    var o4 = 0; var t4;
    var o3 = 0; var t3;
    var o2 = 0; var t2;
    var o1 = 0; var t1;
    var x;
    for(x=0; x<intArr.length; x++) {
        t4 = intArr[x] & 0xFF;
        t3 = (intArr[x] >> 8) & 0xFF;
        t2 = (intArr[x] >> 16) & 0xFF;
        t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
        c4[t4]++;
        c3[t3]++;
        c2[t2]++;
        c1[t1]++;
    }
    for (x=0; x<256; x++) {
        t4 = o4 + c4[x];
        t3 = o3 + c3[x];
        t2 = o2 + c2[x];
        t1 = o1 + c1[x];
        c4[x] = o4;
        c3[x] = o3;
        c2[x] = o2;
        c1[x] = o1;
        o4 = t4;
        o3 = t3;
        o2 = t2;
        o1 = t1;
    }
    for(x=0; x<intArr.length; x++) {
        t4 = intArr[x] & 0xFF;
        cpy[c4[t4]] = intArr[x];
        c4[t4]++;
    }
    for(x=0; x<intArr.length; x++) {
        t3 = (cpy[x] >> 8) & 0xFF;
       
Edit
Report

1 Answer

12

I've tested typed arrays, the QSIP version seems to be good in modern browsers:

2 000 000 elements

          QSIP_TYPED | RDXIP_TYPED |  QSIP_STD | RDXIP_STD
----------------------------------------------------------
Chrome  |    300          1000          600        1300
Firefox |    550          1500          800        1600    

http://jsfiddle.net/u8t2a/35/

Support (source: http://caniuse.com/typedarrays):

 IE 10+   |   FF 4+  |  Chrome 7+  |  Safari 5.1+  |  Opera 11.6+   
answered 2011-11-13T19:32:50.580

Your Answer