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

Revision 4 of this benchmark created by espadrine 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 = [944,446,626,74,770,694,639,441,195,908,568,270,110,777,303,357,278,978,714,50,61,416,517,424,92,905,628,870,463,963,740,612,343,877,409,853,926,373,493,758,23,260,401,214,645,173,240,396,423,131,616,462,768,933,529,333,281,585,540,396,13,830,160,140,852,530,161,191,467,172,375,960,983,945,374,99,766,949,315,308,507,828,136,565,87,790,272,755,516,298,986,777,663,899,466,667,336,588,839,946,737,834,366,411,268,879,143,848,162,219,797,679,414,228,816,413,94,739,353,848,146,27,568,394,450,12,848,531,45,751,494,403,90,191,837,736,374,945,66,855,904,392,429,285,391,673,913,593,253,296,924,406,86,916,992,239,446,512,8,663,141,631,63,551,210,576,524,628,194,442,568,325,319,646,64,958,712,196,310,626,855,277,887,784,46,843,553,378,764,845,923,578,485,373,424,607,669,490,857,903,367,781,749,863,116,656,558,710,580,282,700,619,707,595,347,86,991,239,871,663,803,411,865,622,662,548,686,790,742,515,541,805,869,431,245,307,761,574,913,93,286,870,999,159,69,295,315,587,869,160,875,691,754,667,665,463,272,285,743,345,472,483,383,565,859,114,338,817,107,252,670,825,620,621,26,467,844,846,665,422,574,607,41,19,348,482,232,835,456,650,70,819,980,885,375,203,771,255,317,211,263,724,547,655,520,420,423,797,15,680,337,512,169,100,874,625,857,737,316,528,680,287,768,584,33,541,18,584,667,673,87,556,727,931,330,478,988,136,828,83,333,984,789,743,358,497,644,618,348,178,528,638,769,295,867,611,853,514,903,727,820,533,32,996,760,700,22,710,242,635,297,840,259,737,703,404,199,67,376,205,179,518,606,53,185,367,870,497,185,274,543,357,569,538,123,849,7,970,225,898,123,32,979,313,148,3,941,858,83,808,77,896,756,792,929,199,564,172,552,735,606,112,448,712,407,375,278,938,381,271,788,597,756,205,38,877,691,470,744,482,943,23,230,972,528,957,288,35,495,986,7,243,92,810,455,598,329,417,975,177,183,450,696,481,453,554,825,686,602,238,192,839,734,138,521,193,242,745,898,294,554,581,948,136,828,549,311,697,427,662,110,413,481,650,212,713,874,4,299,571,555,863,903,117,144,774,834,763,442,767,669,976,585,354,253,751,276,79,496,120,731,934,107,508,732,538,271,566,430,271,707,194,376,643,990,802,572,69,476,539,222,863,718,92,234,714,764,921,484,134,306,214,309,327,281,680,666,778,115,289,946,365,499,441,477,162,265,616,341,249,670,493,225,707,140,658,727,716,334,499,653,93,182,617,608,903,447,86,403,767,195,225,561,354,504,76,551,77,691,689,169,447,287,427,893,658,22,935,909,940,124,136,947,901,287,563,50,637,779,661,834,604,300,177,892,368,353,639,501,158,90,0,893,778,833,932,973,865,708,927,519,631,154,298,562,228,338,442,876,614,922,206,246,321,961,33,437,861,153,596,639,580,93,47,433,660,681,602,261,615,322,119,728,79,97,549,31,888,681,598,243,476,351,723,197,364,84,626,234,118,407,736,116,463,345,788,16,382,563,494,608,939,527,475,919,254,329,69,797,503,625,392,563,115,984,2,644,313,844,859,767,15,188,825,615,660,962,813,644,927,297,840,172,465,546,675,717,690,228,432,18,418,19,504,108,623,38,458,317,866,829,68,125,26,564,502,289,797,232,778,814,44,778,12,911,517,428,617,275,617,719,628,638,865,78,488,842,487,146,220,347,64,429,643,408,485,268,427,948,567,569,90,485,570,212,727,346,472,564,151,804,348,73,339,693,379,467,582,526,35,708,465,138,769,476,896,383,91,622,684,499,265,721,828,304,998,601,520,550,359,453,79,356,910,956,465,881,464,628,756,59,133,511,6,499,392,141,176,395,670,709,430,631,582,219,933,70,303,479,443,407,713,722,393,856,929,726,892,372,508,359,26,71,129,582,130,15,867,71,244,521,181,797,792,761,642,83,635,457,7,896,37,111,677,386,772,384,764,979,526,871,944,642,6,770,54,303,684,673,884,782,884,976,978,13,19,214,294,779,130,980,507,655,540,915,357,371,325,709,888,351,558,936,671,725,711,37,62,770,411,744,364,301,775,775,316,263,878,667,651,419,519,220,643,796,347,133,420,279,581,66,527,561,996,534,715,449,618,767,131,401,538,900,186,58,608,637,110,406,308,834,880,216,979,289,518,332,727,394,950,402,733,197,541,715,433,862,144,826,967];

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 < input.length; 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.