What's the fastest way to merge Array's in JavaScript where comparisons are expensive?

I want to merge two Array's in JavaScript. Unfortunately, comparisons of the particular data I am using is expensive. What is the best algorithm to merge my to lists with the least amount of comparisons?

EDIT: I should note that the two Array's are sorted and I would like the merged content to be sorted and have only unique values.

EDIT: By request I will give you my current code, but it really doesn't help..

// Merges arr1 and arr2 (placing the result in arr1)开发者_如何学运维
merge = function(arr1,arr2) {
    if(!arr1.length) {
        Array.prototype.push.apply(arr1,arr2);
        return;
    }
    var j, lj;
    for(var s, i=0, j=0, li=arr1.length, lj=arr2.length; i<li && j<lj;) {
        s = compare(arr1[i], arr2[j]);
        if(s<0) ++i;
        else if(s==0) ++i, ++j;
        else arr1.splice(i,0, arr2[j++]);
    }
    if(j<lj) Array.prototype.push.apply(arr1, arr2.slice(j));
};

This is exactly what merge sort does in the merging step with a minor addition that duplicate elements will be dropped off. Here's the algorithm:

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    if length(left) > 0 
        append left to result
    else  
        append right to result
    return result

Here is a function to make the array unique:

Array.prototype.unique = function () {
    var r = new Array();
    o:for(var i = 0, n = this.length; i < n; i++)
    {
        for(var x = 0, y = r.length; x < y; x++)
        {
            if(r[x]==this[i])
            {
                continue o;
            }
        }
        r[r.length] = this[i];
    }
    return r;
}

To merge Arrays you would do:

var MainArray= arr1.concat(arr2);

Then to remove duplicates:

var MainArray= MainArray.unique();

Then to sort:

var MainArray= MainArray.sort(); //Or you own sort if you have one

I think this sounds along the lines you were looking for, but it might depend on the amount and type of data.

This seems to do it for me using maps to do comparisons instead of a comparison function. It results in more loops though which is often more expensive than the comparison. This was used to right join arrays of objects that had a name attribute. It also had the unique problem of having to modify the existing array vs. creating a new array and assigning. Some reference thing with D3 and force nodes.

function merge(right,left) {
    var map_right = {},
        map_left = {};
    right.forEach(function(n) {
        map_right[n.name] = n;
    });
    left.forEach(function(n) {
        map_left[n.name] = n;
    });
    for(var n in map_left) {
        if (map_right[n] === undefined) {
            left.splice(nodes.indexOf(map_b[n]),1);
        }
    }
    right.forEach(function (n) {
        if (map_left[n.name] === undefined) {
            left.push(n);
        }
    });
}