What's the most efficient way to merge multiple arrays of sorted objects in JavaScript?

Question

Consider four arrays of objects all sorted individually by date

Object: { id: userId, date : date }

Using JavaScript how should I sort these lists into one merged list by date?

Here's a fiddle with the four lists individually pre sorted.

I can post a fiddle with code that generates and sorts the first four lists if needed? — Aaron, Oct 14 '13 at 21:00
Also check http://stackoverflow.com/questions/979256/sorting-an-array-of-javascript-objects?rq=1 — OneOfOne, Oct 14 '13 at 21:01
Sort each list separately and then merge them by comparing the first entries in each list and taking the most recent (or oldest, you didn't say which direction you wanted) and remove it from it's original array. Continue until all the original arrays are empty. It might be less fiddly to work on merging two arrays, then the other two, then the resulting two arrays. It's just like the merge or a mergesort. — Matt Burland, Oct 14 '13 at 21:05
I posted the fiddle, had to quickly put it together sorry for the delay — Aaron, Oct 14 '13 at 21:11
What's the point of sorting the individual arrays first, if your actual objective is to sort the merged array? — Christophe, Oct 14 '13 at 22:36
The point is the lists are already sorted, the code I gave on the fiddle was to give you some data to work with :) — Aaron, Oct 14 '13 at 22:39
ok, makes sense :-) I'd bet using native methods `concat` + `sort` would be just as good as an optimized `for` loop, but I can't prove it! — Christophe, Oct 14 '13 at 23:56

score 4 · Answer 1 · answered Oct 14 '13 at 21:13

If you'll definitely have the arrays passed to you sorted, the most efficient thing I can think of is to make your own merge algorithm. It would be something like this:

var merged = [];
var arrIndex1 = 0;
var arrIndex2 = 0;
var arrIndex3 = 0;
var arrIndex4 = 0;

while (arrIndex1 < arr1.length || arrIndex2 < arr2.length || arrIndex3 < arr3.length || arrIndex4 < arr4.length) {
     var val1 = arrIndex1 < arr1.length ? arr1[arrIndex1].date : Number.POSITIVE_INFINITY;
     var val2 = arrIndex2 < arr1.length ? arr2[arrIndex2].date : Number.POSITIVE_INFINITY;
     var val3 = arrIndex3 < arr1.length ? arr3[arrIndex3].date : Number.POSITIVE_INFINITY;
     var val4 = arrIndex4 < arr1.length ? arr4[arrIndex4].date : Number.POSITIVE_INFINITY;

     if (val1 < val2 && val1 < val3 && val1 < val4) {
          merged.push(arr1[arrIndex1++]); 
     } else if (val2 < val2 && val1 < val3 && val1 < val4) {
          merged.push(arr2[arrIndex2++]); 
     } else if (val3 < val2 && val1 < val3 && val1 < val4) {
          merged.push(arr3[arrIndex3++]); 
     } else {
          merged.push(arr4[arrIndex4++]); 
     }
}

This would be the fastest way. However, the easiest way to code it - if you're not concerned about it being the fastest - is simply to splice the four arrays together, and run them through your activites.sort() function.

Andrew Shepherd · Accepted Answer · 2013-10-14T23:00:05.060

Because I've got something hard to do and need to procrastinate :-) here's a function "mergeSortedArrays".

It can take any number of parameters, so you call it as:

var resultSorted = mergeSortedArrays(resultA, resultB, resultC, resultD);

It's not as good as it could be, because it only merges two arrays at a time. Perhaps the best implementation would simultaneously merge all the arrays at once. (I'm not sure how that would compare though)

The implementation:

function mergeSortedArrays() {
    function merge(arrayOne, arrayTwo) {        
        var totalLength = arrayOne.length + arrayTwo.length;
        var returnArray = new Array(totalLength);
        var iResult = 0;
        var iOne = 0;
        var iTwo = 0;
        for(var i = 0; i < totalLength; ++i) {
            if(iTwo < arrayTwo.length) {
                if(iOne >= arrayOne.length) {
                    returnArray[i] = arrayTwo[iTwo++];                    
                } else if (arrayOne[iOne].date < arrayTwo[iTwo].date) {
                    returnArray[i] = arrayOne[iOne++];
                } else {
                    returnArray[i] = arrayTwo[iTwo++];
                }  
            } else {
                returnArray[i] = arrayOne[iOne++];
            }
        }
        return returnArray;
    }
    var sortedArray = [];
    for(var i = 0; i < arguments.length; ++i) {
        sortedArray = merge(sortedArray, arguments[i]);
    }
    return sortedArray;
}

Here's the jsFiddle

What's the most efficient way to merge multiple arrays of sorted objects in JavaScript?

2 Answers2