Efficient synchronization of two instances of an ordered list
For synchronizing from a master list to a slave list, it looks like a fellow named Michael Heyeck has a good, O(n) solution to this problem. Check out that blog post for an explanation and some code. Perhaps this is a good starting point to generalize to a two-way sync.

Essentially, the solution tracks both the master and slave lists in a single pass, tracking indices into each. Two data structures are then managed: a list of insertions to be replayed on the slave list, and a list of deletions.

It looks straightforward and also has the benefit of a proof of minimalism, which Heyeck followed up with in a subsequent post. The code snippet in this post is more compact, as well:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x &lt; len(a)) or (y &lt; len(b)):
    if y &gt;= len(b): d.append(x); x += 1
    elif x &gt;= len(a): i.append((y, b[y])); y += 1
    elif a[x] &lt; b[y]: d.append(x); x += 1
    elif a[x] &gt; b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)


Again, credit to Michael Heyeck.