How can I push an element into array at a sorted index position?

If it is a very long list, you don't want to sort the list everytime. A sorting with floats is at best O(n*log n). If you do a linear search you will have O(n) instead.

function search(a, v) {
    if(a[0]['price'] > v['price']) {
        return 0;
    }
    var i=1;
    while (i<a.length && !(a[i]['price'] > v['price'] && a[i-1]['price'] <= v['price'])) {
        i=i+1;
        }
    return i;
}

myArray.splice(search(myArray, newItem), 0, newItem)

However, if the list is VERY long it would be a good idea to do a binary search instead of a linear search. That would take it down to O(log n). A binary search is pretty simple. You start in the middle. If the element is larger than what you're searching for, apply the same algorithm to the upper half of the list, otherwise to lower part. It's easy to find code examples of binary search on the web.

Here is an example:

function binarySearch(ar, el, compare_fn) {
    if (el.price < ar[0].price)
        return 0;
    if (el.price > ar[ar.length-1].price)
        return ar.length;
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

function comp(a, b) {
    return a['price']>b['price']
}

myArray.splice(binarySearch(myArray, element, comp), 0, element)

(Stolen from here Binary Search in Javascript)

But to wrap it up. Adding the element and then sorting is usually a bad idea. Best case is that it does not matter, but since you know that the list is sorted, why not do at least a linear search?

If the lists are small, this does not matter, but if the lists have millions of elements the difference will be quite noticeable.

EDIT:

I made a quick and primitive benchmark.

            10,000   100,000  1000,000   10,000,000  
Sort            80       900     13000          N/A
Linear           2         2        25         5000
Binary           2         2         5           21

I measured the time it took to run the three algorithms on four different sizes. I did not want to wait for the sorting to end on ten million elements. Therefore the N/A. Time is in milliseconds. Note that the benchmark were very primitive, but it gives an idea about how much it affects when sizes grow.


To avoid sorting your array each time, you can iterate through your array until an element with greater price is found, and then use array.splice(index, 0, element) to insert your element into the correct position:

var array = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

function insertSorted (array, element, comparator) {
  for (var i = 0; i < array.length && comparator(array[i], element) < 0; i++) {}
  array.splice(i, 0, element)
}

function compareByPrice (a, b) { return a.price - b.price }

insertSorted(array, { title: "Article 5", price: 12.00 }, compareByPrice)

console.log(array)