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

Revision 9 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 use linear search as a baseline.

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;
};
function findIndexOf(el, arr) {
  for (var i = 0; arr[i] < el; i++) {}
  return i;
}
</script>

Setup

// Pseudo-random data.
    // I keep it the same for the sake of comparison.
    var input = [];
    for(i=0;i<300000;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; i < input.length; i++) {
  arr.push(input[i]);
}
arr.sort(function(a,b){return a-b;});
ready
Linear search
var arr = [];
var pos;
for (var i = 0; i < 0; i++) {
  pos = findIndexOf(input[i], arr);
  arr.splice(pos, 0, input[i]);
}
ready
Binary search
var arr = [];
var pos;
for (var i = 0; i < input.length; 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.