A JavaScript algorithm I came up with to calculate the operations to be applied to an array L to make it the same as a new array R when it is undesirable to simply replace L with R. Typically this is when doing so is a costly operation (such as when the elements represent the items of a DOM collection) and/or each component of the update require…

computeArrayUpdateOperations.js

// both arrays should be presorted
function computeArrayUpdateOperations(oldarr, newarr, compare) {
    if (!compare)
        compare = computeArrayUpdateOperations.compare;
    var l = 0, r = 0, p = 0,
    op = null, ops = [],
    leof = l >= oldarr.length, reof = r >= newarr.length;
    while (!(leof && reof)) {
        if (!leof && (reof || compare(oldarr[l], newarr[r]) < 0)) {
            if (op && op[0] === 'i')
                op = null;
            if (!op)
                ops.push(op = ['r', p, 1, oldarr[l]]);
            else {
                op[2]++;
                op.push(oldarr[l]);
            }
            l++;
        }
        else if (!reof && (leof || compare(oldarr[l], newarr[r]) > 0)) {
            if (op && op[0] === 'r')
                op = null;
            if (!op)
                ops.push(op = ['i', p, 1, newarr[r]]);
            else {
                op[2]++;
                op.push(newarr[r]);
            }
            p++;
            r++;
        }
        else {
            l++;
            r++;
            p++;
            op = null;
        }
        leof = l >= oldarr.length;
        reof = r >= newarr.length;
    }
    return ops;
}
computeArrayUpdateOperations.compare = function (a, b) {
    return a > b ? 1 : a < b ? -1 : 0;
};