Efficient way to insert a number into a sorted array of numbers?

Elliot Kroo picture Elliot Kroo · Aug 28, 2009 · Viewed 100.7k times · Source

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:

  • Best case for several insertion algorithms is O(n), which is still significantly different from O(log(n)), but not quite as bad as O(n log(n)) as mentioned below. It would come down to the particular sorting algorithm used (see Javascript Array.sort implementation?)
  • The sort method in JavaScript is a native function, so potentially realizing huge benefits -- O(log(n)) with a huge coefficient can still be much worse than O(n) for reasonably sized data sets.

Answer

Sam Phillips picture Sam Phillips · Nov 19, 2010

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