Inserting into a sorted array

JavaScript performance comparison

Revision 3 of this test case created

Preparation code

<script>
  var findLocationFor = function(n, arr) {
      var i = Math.floor(arr.length / 2);
      var prev_i = arr.length;
      while (1) {
        var b = i;
        if (arr[i] === n) return i + 1;
        if (arr[i] < n) {
          if (i === arr.length - 1 || arr[i + 1] > n) {
            return i + 1;
          }
 
          i += Math.floor(Math.abs(prev_i - i) / 2);
        } else // arr[i] > n
        {
          if (i === 0 || arr[i - 1] < n) {
            return i + 1;
          }
 
          i -= Math.floor(Math.abs(prev_i - i) / 2);
        }
        prev_i = b;
      }
      }

var findIndexOf = function(n, array) {
    var low = 0, high = array.length;
    while (low < high) {
      var mid = (low + high) >>> 1;
      array[mid] < n ? low = mid + 1 : high = mid;
    }
    return low;
  };
</script>
<script>
Benchmark.prototype.setup = function() {
    var largeArray = [];
    for (var n = 0; n < 10000; n++) {
      largeArray.push(n);
    }
   
    var newVal = 1337.5;
};

Benchmark.prototype.teardown = function() {
    delete largeArray;
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
push() and sort()
largeArray.push(newVal);
largeArray.sort(function(a, b) {
  return a - b;
});
pending…
splice()
var newPos = findLocationFor(newVal, largeArray);
largeArray.splice(newPos, 0, newVal);
pending…
binary search
var newPos = findIndexOf(newVal, largeArray);
largeArray.splice(newPos, 0, newVal);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment