How to most efficiently merge and sort arrays of dicts with datetime in javascript?

Question

Assume I have the following 3 arrays which are sorted in ascending order by exercisedateandtime:

var listA = [
  {name: "Mike", exercisedateandtime: 1299233593000, exercise: "Jumping Jacks"}, 
  {name: "Mike", exercisedateandtime: 1299237012000, exercise: "Running"}
];

var listB = [
  {name: "Charles", exercisedateandtime: 1299233712000, exercise: "Swimming"},
  {name: "Charles", exercisedateandtime: 1299233831000, exercise: "Swimming"},
  {name: "Charles", exercisedateandtime: 1299240620000, exercise: "Swimming"}
];

var listC = [
{name: "William", exercisedateandtime: 1299237320000, exercise: "Fishing"},
{name: "William", exercisedateandtime: 1299237611000, exercise: "Motor Boating"},
{name: "William", exercisedateandtime: 1299305420000, exercise: "Cycling"}
];

What is the most efficient way to merge these lists such that I get a resulting array listD is also sorted in ascending order by exercisedateandtime? Is it possible to create a function that accepts any number of arrays? (Note: Though the sample provided is small, the ideal method should be handle large list(s) sizes.)

var listD = [
{name: "Mike", exercisedateandtime: 1299233593000, exercise: "Jumping Jacks"},
{name: "Charles", exercisedateandtime: 1299233712000, exercise: "Swimming"},
{name: "Charles", exercisedateandtime: 1299233831000, exercise: "Swimming"},
{name: "Mike", exercisedateandtime: 1299237012000, exercise: "Running"},
{name: "William", exercisedateandtime: 1299237320000, exercise: "Fishing"},
{name: "William", exercisedateandtime: 1299237611000, exercise: "Motor Boating"},
{name: "Charles", exercisedateandtime: 1299240620000, exercise: "Swimming"},
{name: "William", exercisedateandtime: 1299305420000, exercise: "Cycling"}
];

Answer 1

var listD = listA.concat(listB, listC).sort(function(a, b) {
    return a.exercisedateandtime - b.exercisedateandtime
});

Answer 2

This seems like it is just a slight adaptation of a merge in a normal mergesort (runs in O(n)). Basically how that works is you keep looking at the beginning of each list and and taking the largest the smallest one an appending it to the new list it works exactly the same for three lists . So this is the code from Aadit's solution(same algo as mine), but everyone seems to be up-voting a solution that is significantly slower than this solution and I would like to counter act this so the OP doesn't end up using it in his code.

function merge(key) {
    var length = arguments.length, lists = [], newlist = [];
    for (var i = 1; i < length; i++) lists.push(arguments[i].slice());

    while (length = lists.length) {
        var min = Infinity;

        for (var i = 0; i < length; i++) {
            var list = lists[i];
            var value = list[0][key];

            if (value < min) {
                var index = i;
                min = value;
            }
        }

        var list = lists[index];
        newlist.push(list.shift());
        if (!list.length) lists.splice(index, 1);
    }

    return newlist;
}

Now you can merge the lists as follows:

var listD = merge("exercisedateandtime", listA, listB, listC);  

Basically how this works is is gets an list of lists and the key that it is supposed to sort by, in this case exercisedateandtime. Then it keeps finding the minimum front element of all the list until there are no lists left(the while loop is a little tricky since the = returns whatever is the value it is set to when lists is 0 it becomes false). This merge will work with any number of lists even if they are different sizes. This algorithm runs in O(n) assuming the list sizes are large enough to make the number of lists negligible.

EDIT: in an extremely unideal case where the number of lists is very large, which is not the case here as there are only three lists, and the size of each list is small it might be better to do a solution where the lists are merged like in a merge sort, 2 at a time. The code could be adapted to do this by checking the number of lists but it would be a lot more work to code. I'll also repeat one more time that the original question is for 3 lists so it will work fine for that.

Here is a link to the most ideal n-way merge I could find

Answer 3

Yes, indeed. Try this:

function merge(key) {
    var length = arguments.length, lists = [], newlist = [];
    for (var i = 1; i < length; i++) lists.push(arguments[i].slice());

    while (length = lists.length) {
        var min = Infinity;

        for (var i = 0; i < length; i++) {
            var list = lists[i];
            var value = list[0][key];

            if (value < min) {
                var index = i;
                min = value;
            }
        }

        var list = lists[index];
        newlist.push(list.shift());
        if (!list.length) lists.splice(index, 1);
    }

    return newlist;
}

Now you can merge the lists as follows:

var listD = merge("exercisedateandtime", listA, listB, listC);

See the demo here: http://jsfiddle.net/b8WdW/2/

Answer 4

Fiddle

Basically I merged the arrays first before sorting them. So this should work even if you arrays are unsorted.

var listD = listB.concat(listA, listC);
console.log(listD);
listD.sort(function (a, b) {
return a.exercisedateandtime - b.exercisedateandtime
});
console.log(listD);