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

Question

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-1;
  var pivot = parseInt(start + (end - start) / 2);
  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);
  }
}

print(insert(element, array));

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;
}

print(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 http://stackoverflow.com/questions/234683/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 1

Your insertion function assumes that the given array is sorted, it searches directly for the location where the new element can be inserted, usually by just looking at a few of the elements in the array.

The general sort function of an array can't take these shortcuts. Obviously it at least has to inspect all elements in the array to see if they are already correctly ordered. This fact alone makes the general sort slower than the insertion function.

A generic sort algorithm is usually on average O(n*log(n()) and depending on the implementation it might actually be the worst case if the array is already sorted, leading to complexities of O(n^2). Directly searching for the insertion position instead has just a complexity of O(log(n)), so it will always be much faster.

Answer 2

Here are a few thoughts: Firstly, if you're genuinely concerned about the runtime of your code, be sure to know what happens when you call the built-in functions! I don't know up from down in javascript, but a quick google of the splice function returned this, which seems to indicate that you're creating a whole new array each call! I don't know if it actually matters, but it is certainly related to efficiency. I see that Breton, in the comments, has already pointed this out, but it certainly holds for whatever array-manipulating function you choose.

Anyways, onto actually solving the problem.

When I read that you wanted to sort, my first thought is to use insertion sort!. It is handy because it runs in linear time on sorted, or nearly-sorted lists. As your arrays will have only 1 element out of order, that counts as nearly-sorted (except for, well, arrays of size 2 or 3 or whatever, but at that point, c'mon). Now, implementing the sort isn't too too bad, but it is a hassle you may not want to deal with, and again, I don't know a thing about javascript and if it will be easy or hard or whatnot. This removes the need for your lookup function, and you just push (as Breton suggested).

Secondly, your "quicksort-esque" lookup function seems to be a binary search algorithm! It is a very nice algorithm, intuitive and fast, but with one catch: it is notoriously difficult to implement correctly. I won't dare say if yours is correct or not (I hope it is, of course! :)), but be wary if you want to use it.

Anyways, summary: using "push" with insertion sort will work in linear time (assuming the rest of the array is sorted), and avoid any messy binary search algorithm requirements. I don't know if this is the best way (underlying implementation of arrays, maybe a crazy built-in function does it better, who knows), but it seems reasonable to me. :) - Agor.

Answer 3

You should also take into consideration that depending on javascript implementation built in functions might be implemented in native code, and thus be a lot faster then your own JS code. And although your algorithm has lower complexity, sort + push might be faster.