title: Algorithm to get changes between two arrays
body: <p>I needed to create an algorithm which will (efficiently) take an old array and a new array and give me back the changes between the two (which items added, which removed). It happens to need to be in JavaScript (to run in the browser) but the algorithm's more important than the language.</p>
  
  <p>This is what I came up with: <a href="http://jsbin.com/osewu3/13" rel="noreferrer">http://jsbin.com/osewu3/13</a>. Can anyone see any problems with that/suggest any improvements?</p>
  
  <p>Thanks!</p>
  
  <p>Code Listing:</p>
  
  <pre><code>function diff(o, n) {
    // deal with empty lists
    if (o == undefined) o = [];
    if (n == undefined) n = [];
  
    // sort both arrays (or this won't work)
    o.sort(); n.sort();
  
    // don't compare if either list is empty
    if (o.length == 0 || n.length == 0) return {added: n, removed: o};
  
    // declare temporary variables
    var op = 0; var np = 0;
    var a = []; var r = [];
  
    // compare arrays and add to add or remove lists
    while (op &lt; o.length &amp;&amp; np &lt; n.length) {
        if (o[op] &lt; n[np]) {
            // push to diff?
            r.push(o[op]);
            op++;
        }
        else if (o[op] &gt; n[np]) {
            // push to diff?
            a.push(n[np]);
            np++;
        }
        else {
            op++;np++;
        }
    }
  
    // add remaining items
    if( np &lt; n.length )
      a = a.concat(n.slice(np, n.length));
    if( op &lt; o.length )
      r = r.concat(o.slice(op, o.length));
  
    return {added: a, removed: r}; 
  }
  </code></pre>
  
  <p>(I have also posted this as a potential solution to another SO question, here: <a href="https://stackoverflow.com/questions/1187518/javascript-array-difference/3476612#3476612">JavaScript array difference</a>)</p>