Radix Sort (v5)

Revision 5 of this benchmark created on

Setup

function generate(num) {
    var result = []; for ( var idx = 0; idx < num; ++idx) { result.push(~~(Math.random()*100)); } return result;
    }
    
    function radix_sort(arr, idx_begin, idx_end, bit) {
        if (!Array.isArray(arr)) return;
        idx_begin = (typeof idx_begin === 'undefined') ? 0 : idx_begin;
        idx_end = (typeof idx_end === 'undefined') ? arr.length : idx_end;
        bit = (typeof bit === 'undefined') ? 31 : bit;
        if (idx_begin >= (idx_end - 1) || bit < 0) {
            return;
        }
        var idx = idx_begin;
        var idx_ones = idx_end;
        mask = 0x1 << bit;
        while (idx < idx_ones) {
            if (arr[idx] & mask) {
                --idx_ones;
                var tmp = arr[idx];
                arr[idx] = arr[idx_ones];
                arr[idx_ones] = tmp;
            } else {
                ++idx;
            }
        }
        radix_sort(arr, idx_begin, idx_ones, bit-1);
        radix_sort(arr, idx_ones, idx_end, bit-1);
    }
    
    var altRadixSort = function(input) {
    
      var digits = Math.ceil(Math.log(Math.max.apply(null, input)) / Math.log(10));
    
      for (var i = 0; i < digits; i++) {
        for (var j = 9; j >= 0; j--) {
          for ( var k = 0, p = 0; k < input.length; k++) {
            var aAtDigit = Math.floor( input[k] / Math.pow(10, i)) % 10;
            if (aAtDigit === j) {
              input.splice(p++, 0, input.splice(k, 1)[0]);
            }
          }
        }
      }
      return input;
    };

Test runner

Ready to run.

Testing in
TestOps/sec
MSB Radix Sort
var arr = generate(10000);
radix_sort(arr);
ready
Normal Sort
var arr = generate(10000);
arr.sort();
ready
altRadixSort
var arr = generate(10000);
altRadixSort(arr);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.