Inserting into a sorted array

JavaScript performance comparison

Revision 2 of this test case created and last updated

Preparation code

<script>
   function getRandom() {
       return Math.floor(Math.random() * 10000);
   }

  var findLocationLogarithmic = function(n, arr) {
                var left = 0;
                var right = arr.length - 1;
                while (left <= right){
                    var mid = Math.floor((left + right) / 2);
                    if (arr[mid] == n)
                        return mid;
                    else if (arr[mid] < n)
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                return arr.length;
      }
     
     
     
  var findLocationLinear = function(n, arr) {
      var i, len = arr.length;
      for (i = 0; i < len; i++) {
        if (arr[i] >= n) return i;
      }
      return len;
      }
</script>
<script>
Benchmark.prototype.setup = function() {
    var largeArray = [];
    for (var n = 0; n < 10000; n++) {
      largeArray.push(n);
    }
};

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()
var newVal = getRandom();
largeArray.push(newVal);
largeArray.sort(function(a, b) {
  return a - b;
});
pending…
splice() with logarithmic search
var newVal = getRandom();
var newPos = findLocationLogarithmic(newVal, largeArray);
largeArray.splice(newPos, 0, newVal);
pending…
splice() with linear search
var newVal = getRandom();
var newPos = findLocationLinear(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