Benchmarking javascript inserting a new element into a sorted array – three approaches

Task: having a sorted array add one value so that the array remains sorted in browser-based JavaScript.

Assumption: internal array sort may win to some extent over interpreted search and insert.

What I did is implemented all three algorithms and made a post to demonstrate the results of the benchmarking.

Tests are run in async mode to allow Google Charts do their work and prevent browser freezing. Sync mode will give more accurate results, though.

Each method is run several times against a starting array of the same size. On next benchmark cycle the size of array doubles until the [cci]maxSize[/cci] limit is reached.

The benchmarking library only takes into account the wall time. Though linear is faster on low array sizes (less than 64 in my case), it is more CPU intensive.

Feel free to run [cci lang=”javascript”]runTest(size)[/cci] in console. Bear in mind that the chart may break if size is less than previous displayed.

You can set maxSize param in url. For 65536 use this link

Results: Internal [cci]Array.sort()[/cci] shouldn’t be preferred over logarithmic or even linear search for all cases. Logarithmic search also has lower CPU usage. No wonder, though. Use logarithmic FTW.

The code

[cc lang=”javascript”]
/*
* A simplest method that comes at the first sight.
* O(1) JavaScript interpreted insert and then the sort
* that is probably implemented as a precompiled method
* (or not?), but should take at least O(n*ln(n))
*/
Array.prototype.addSorted1 = function(element){
this.push(element);
this.sort();
return this;
}
[/cc]

vs

[cc lang=”javascript”]
/*
* An O(n) JavaScript interpreted new element inserter
*/
Array.prototype.addSorted2 = function(element){
for(var i=0;i<;this.length && this[i] < element;i++){ } this.splice(i,0,element); return this; } [/cc]

vs

[cc lang=”javascript”]
/*
* An O(ln(n)) JavaScript interpreted new element inserter
*/
Array.prototype.addSorted3 = function(element){
var i=0;
var j=this.length;
var h;
var c=false;
if (element>this[j]){
this.push(element);
return this;
}
if (elementthis[h]){
i=h;
} else {
j=h;
}
if (j-i<=1){ this.splice(j,0,element); c=true; } } return this; }; [/cc]

The benchmark

Start Benchmark

After starting the benchmark, please wait for a minute or two… or check your console for errors 🙂
Logs: