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

I have measured the results of three different algorithms in three different browsers.

In all performance-related questions, there are two things:

• If you really want to know the answer, you have to test your specific algorithm across multiple browsers to actually answer the question.

• Many of the performance issues are actually not material in the given context in which they are used, so worrying about them until you know you need to worry about them is nothing more than wasted time about premature optimization or even unnecessary optimization. Therefore, before working on a specific area of ​​performance, you should know that it is important and know that it is worth investing the time.

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

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

Algorithm 1 is concatenated and then sorts the concatenated array. In JS, this is nothing more:

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

      

        
        
        
      

    

Algorithm 2 - Attempt to sort the insert. The basic idea is to iterate over the second array and, for each element in that array, find where to insert it into the first array. Since both arrays are sorted, we only need to look for a place to insert the next element into the first array at the position after we inserted the last element.

Algorithm 3 is merge sort. The idea here is that you create an empty results array and two indices, one for each of the two original arrays. For the value at each source index, you insert the result at the lower of the two elements and then increment the source index. Whenever the original index is exhausted, you push the rest of the other array. I assumed it would be more efficient than insertion sort because it doesn't need to insert elements in the middle of the array, just add to the end, which will likely speed things up.

To run the test, I created two arrays, each containing 100 objects. Each object has a numeric property that is assigned a random number between 0 and 100,000. Then, each of the two source arrays is pre-sorted. Then each algorithm is tested against these two original 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/