Radix Sort (v6)

Revision 6 of this benchmark created by fhb on

Setup

function generate(num) {
      var result = [];
      for ( var idx = 0; idx < num; ++idx) {
        result.push(~~(Math.random()*1e9));
      }
      return result;
    }
    
    function radix_sort(arr) {
      if (!Array.isArray(arr)) return;
    
      function sort(arr, idx_begin, idx_end, bit) {
        var idx,
            idx_ones,
            mask,
            tmp;
    
        if (idx_begin >= (idx_end - 1) || bit < 0) {
          return;
        }
    
        idx = idx_begin;
        idx_ones = idx_end;
        mask = 0x1 << bit;
    
        while (idx < idx_ones) {
          if (arr[idx] & mask) {
            --idx_ones;
            tmp = arr[idx];
            arr[idx] = arr[idx_ones];
            arr[idx_ones] = tmp;
          } else {
            ++idx;
          }
        }
        sort(arr, idx_begin, idx_ones, bit - 1);
        sort(arr, idx_ones, idx_end, bit - 1);
      }
    
      sort(arr, 0, arr.length, 31);
    }
    
    function altRadixSort(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(function (a, b) { return a - b; });
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.