I have a sorted JavaScript array, and want to insert one more item into the array such the resulting array remains sorted. I could certainly implement a simple quicksort-style insertion function:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.splice(locationOf(element, array) + 1, 0, element);
return array;
}
function locationOf(element, array, start, end) {
start = start || 0;
end = end || array.length;
var pivot = parseInt(start + (end - start) / 2, 10);
if (end-start <= 1 || array[pivot] === element) return pivot;
if (array[pivot] < element) {
return locationOf(element, array, pivot, end);
} else {
return locationOf(element, array, start, pivot);
}
}
console.log(insert(element, array));
[WARNING] this code has a bug when trying to insert to the beginning of the array, e.g. insert(2, [3, 7 ,9]
) produces incorrect [ 3, 2, 7, 9 ].
However, I noticed that implementations of the Array.sort function might potentially do this for me, and natively:
var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
array.push(element);
array.sort(function(a, b) {
return a - b;
});
return array;
}
console.log(insert(element, array));
Is there a good reason to choose the first implementation over the second?
Edit: Note that for the general case, an O(log(n)) insertion (as implemented in the first example) will be faster than a generic sorting algorithm; however this is not necessarily the case for JavaScript in particular. Note that:
Just as a single data point, for kicks I tested this out inserting 1000 random elements into an array of 100,000 pre-sorted numbers using the two methods using Chrome on Windows 7:
First Method:
~54 milliseconds
Second Method:
~57 seconds
So, at least on this setup, the native method doesn't make up for it. This is true even for small data sets, inserting 100 elements into an array of 1000:
First Method:
1 milliseconds
Second Method:
34 milliseconds