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

JavaScript performance comparison

Revision 7 of this test case created

Info

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 code

<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>
<script>
Benchmark.prototype.setup = function() {
    // 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()));
};
</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 arr = [];
for (var i = 0; i < input.length; i++) {
  arr.push(input[i]);
}
arr.sort(function(a,b){return a-b;});
pending…
Linear search
var arr = [];
var pos;
for (var i = 0; i < input.length; i++) {
  pos = findIndexOf(input[i], arr);
  arr.splice(pos, 0, input[i]);
}
pending…
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]);
}
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