diff & patch the array, using DP.

diff.js

'use strict'
module.exports = diff

const MATCH = 0
const REMOVE = 1
const INSERT = 2
const REPLACE = 3

function diff (fromArr, toArr, diffKey) {
  const len1 = fromArr.length
  const len2 = toArr.length

  const dis = []
  const patchArr = []

  dis[0] = [0]
  patchArr[0] = []

  for (let i = 1; i <= len1; i++) {
    dis[i] = [i]
    const patch = {from: {x: i - 1, y: 0}, type: REMOVE}
    patchArr[i] = [patch]
  }

  for (let i = 1; i <= len2; i++) {
    dis[0][i] = i
    const patch = {from: {x: 0, y: i - 1}, type: INSERT}
    patchArr[0][i] = patch
  }

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      const fromKey = getDiffV(fromArr[i - 1], diffKey)
      const toKey = getDiffV(toArr[j - 1], diffKey)
      const cost = fromKey === toKey
        ? 0 : 2

      if (cost === 0) { //no patch
        dis[i][j] = dis[i - 1][j - 1]
        patchArr[i][j] = {from: {x: i - 1, y: j - 1}, type: MATCH}
      }
      else {
        const insert = dis[i][j - 1] + 1
        const remove = dis[i - 1][j] + 1
        const replace = dis[i - 1][j - 1] + cost
        const minDis = Math.min(remove, insert, replace)
        const patch = []

        if (remove === minDis) {
          patch.push({from: {x: i - 1, y: j}, type: REMOVE})
        }

        if (insert === minDis) {
          patch.push({from: {x: i, y: j - 1}, type: INSERT})
        }

        if (replace === minDis) {
          patch.push({from: {x: i - 1, y: j - 1}, type: REPLACE})
        }

        patchArr[i][j] = patch.length > 1 ? patch : patch[0]
        dis[i][j] = minDis
      }
    }
  }

  const startP = patchArr[len1][len2]
  return getPatch(patchArr, startP, toArr)
}

// todo getAllPatches()

function getPatch (patchArr, curP, toArr) {
  curP = Array.isArray(curP) ? curP[0] : curP
  const {type, from: {x, y}} = curP
  const patch = {index: x, type: type}

  if (type === INSERT || type === REPLACE) {
    patch.item = toArr[y]
  }

  if (x === 0 && y === 0) { // end
    return [patch]
  }

  if (type === 0) { // match, no need to patch
    return getPatch(patchArr, patchArr[x][y], toArr)
  }

  return [patch, ...getPatch(patchArr, patchArr[x][y], toArr)]
}

function getDiffV (item, diffKey = x => x) {
  return typeof diffKey === 'string'
    ? item[diffKey] // callable collection
    : diffKey(item) // function
}

//////////////////////////////////////

'use strict'

const diff = require('./diffArray')

function fix (oldArr, patches) {
  patches.forEach(patch => {
    if (patch.type === 1) {
      oldArr.splice(patch.index, 1) // removing
    }
    else if (patch.type === 2) {
      oldArr.splice(patch.index, 0, patch.item) // insert
    }
    else {
      oldArr.splice(patch.index, 1, patch.item) // replace
    }
  })

  return oldArr
}

const arr1 = [{id: "a"}, {id: "b"}, {id: "c"}, {id: "d"}, {id: "e"}]
const arr2 = [{id: "c"}, {id: "a"}, {id: "b"}, {id: "e"}, {id: "f"}]

const patches = diff(arr1, arr2, 'id')
fix(arr1, patches)

console.log(patches)
console.log(arr1)