Maintaining a sorted array vs. push() and sort() (v8)

Revision 8 of this benchmark created on

Description

The actual use-case isn't to sort for every insertion. Either you keep a sorted array, or you sort it at the end.

I removed linear search because it's so slow that freezes the browser.

Preparation HTML

<script>
function findBSearch(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>

Setup

// Pseudo-random data.
    // I keep it the same for the sake of comparison.
    var input = [];
    for(i=0;i<30000;i++) input.push(Math.floor(Math.random()));

Test runner

Ready to run.

Testing in
TestOps/sec
push() and sort()
var arr = [];
for (var i = 0, l = input.length; i < l; i++) {
  arr.push(input[i]);
}
arr.sort(function(a,b){return a-b;});
ready
Binary search
var arr = [];
var pos;
for (var i = 0, l = input.length; i < l; i++) {
  pos = findBSearch(input[i], arr);
  arr.splice(pos, 0, input[i]);
}
ready

Revisions

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