Is sorting or inserting more efficient with joining arrays of objects in javascript?

Question

I have multiple objects with a field called "num". Num can be any number between 1000000000 to 10000000005. I want to ensure that if I have x number of lists, all lists need to be combined in array1 in sorted ascending order based on the "num" property.

If I start with an array like this "

array1": [{item:23532532, num:1000000520},{item:23523, num:1000000620},{item:346346432, num:1000000620}]

I have a second array

"array2": [{item:23532, num:....},{item:3623, num:....}]

Assuming array2 is in sorted order by "num", is it more efficient to:

1) Add Then Sort Whole - Loop through every item in "array2" and add it to the end of "array1", then do a javascript built in "sort" function on the "num" property on the entire array?

2) Insert Into Right Place - Loop through every item in "array2" and use "if" conditions to check to see if the "num" value is greater than the current item in "array2", if so, then insert the element before that index via "splice". (No javascript built-in array sort used)

Or is there a more efficient method? Pseudocode or sample code is a plus.

Answer 1

I measured the results from three different algorithms in three different browsers.

Two things are true about all performance related questions:

1. If you really want to know the answer, you've got to test your specific algorithm in several browsers to really answer the question.

2. Many performance related questions are actually not material in the given context in which they are being used so worrying about them until you know you need to worry about them is nothing more than time wasted on premature optimization or even unnecessary optimization. So, before working on a specific area of performance, you should know that it matters and know that it's worth spending time on.

That said, here are some measurements for three algorithms. This assumes you start with two arrays of objects, each sorted independently by one particular numeric property that is present in each object.

Here's the jsperf: http://jsperf.com/concat-sort-vs-insert-sort/5 that has the code for each of the three algorithms.

Algorithm 1 is concatenate and then sort the concatenated array. In JS, it's nothing more than:

var result = arr1.concat(arr2);
result.sort(sortByNum);

Algorithm 2 is an attempt at an insertion sort. The basic idea is to loop through the second array and for each item in that array, find where to insert it into the first array. Since both arrays are sorted, we only have to start looking for a place to insert the next item into the first array at the place after where we inserted the last item.

Algorithm 3 is a merge sort. The idea here is that you create an empty result array and two indexes, one for each of the two source arrays. For the value at each source index, you push into the result the lower of the two items and then increase its source index. When either source index is exhausted, you push in the rest of the other array. I was guessing that it would be more efficient than the insertion sort because it doesn't have to insert items into the middle of an array, just add onto the end which is likely a faster operation.

---

To run a test, I created two arrays that each contain 100 objects. Each object has a numeric property that is assigned a random number between 0 and 100,000. Each of the two source arrays are then pre-sorted. Each algorithm is then tested on these two source arrays.

And, here are the results:

Here's the code for the merge sort algorithm:

function mergeSort(arr1, arr2) {
    var result = [];
    var index1 = 0;
    var index2 = 0;
    if (!arr1.length) {
        return arr2.slice(0);
    } else if (!arr2.length) {
        return arr1.slice(0);
    }
    while (true) {
        if (arr1[index1].num <= arr2[index2].num) {
            result.push(arr1[index1]);
            ++index1;
            // see if we reached the end of the array
            if (index1 >= arr1.length) {
                result.push.apply(result, arr2.slice(index2));
                break;
            }
        } else {
            result.push(arr2[index2]);
            ++index2;
            // see if we reached the end of the array
            if (index2 >= arr2.length) {
                result.push.apply(result, arr1.slice(index1));
                break;
            }
        }
    }
    return result;
}

Working demo: http://jsfiddle.net/jfriend00/mja1c13d/