Differ - C# class that performs an inspection of two sorted lists to identify differences and orphans.

Differ.cs

using System.Collections.Generic;

namespace Console
{
    /// <summary>
    /// Performs an inspection of two sorted lists to identify differences and orphans.
    /// </summary>
    class Differ
    {
        /// <summary>
        /// Walks two sorted lists in concert, finding differences (item matches with version diffs, or left/right hand orphan items)
        /// </summary>
        public IEnumerable<Difference> IdentifyDifferences(IEnumerable<dynamic> source, IEnumerable<dynamic> target)
        {
            var iter = target.GetEnumerator();
            dynamic t = null;
            bool getNextT = iter.MoveNext(); // iter.Current throws once we deplete the iterator, so hang on to the last test.

            foreach (dynamic s in source)
            {
            TopOfLoop:

                t = (getNextT) ? iter.Current : null;

                if (t != null)
                {
                    switch ((The)CheckItems(s, t))
                    {
                        case The.IdsMatch:
                            if (s.Version != t.Version)
                                yield return ItemDifference(s, t);
                            // else... we're in sync!  Either way, set up for the next pass.

                            getNextT = iter.MoveNext(); // t + 1
                            continue; // s + 1

                        case The.TargetIsMissingId:
                            yield return MissingItem(s);

                            // don't advance the iter: the next source item may be the one matching the target
                            continue;

                        case The.TargetHasUnexpectedId:
                            yield return UnexpectedItem(t);

                            // we want to test this same source item against the next target, hoping we find it, so...
                            getNextT = iter.MoveNext();
                            goto TopOfLoop; // yeah, "goto."  I went there.
                    }
                }
                else // from here, everything in the source is not in the target
                    yield return MissingItem(s);
            }

            if (getNextT) // if this is still true, we exhausted the source and still have targets.
                do
                { // so mark everything in the target as unexpected.
                    yield return UnexpectedItem(iter.Current);
                } while (iter.MoveNext());
        }

        /// <summary>
        /// Tests the ids of two items and returns an enum describing their relationship.
        /// </summary>
        private static The CheckItems(dynamic src, dynamic tgt)
        {
            return (The)Comparer<int>.Default.Compare(src.Id, tgt.Id);
        }

        #region Factory methods
        private static Difference ItemDifference(dynamic s, dynamic t)
        {
            return new Difference() { Id = s.Id, SourceVer = s.Version, TargetVer = t.Version };
        }

        private static Difference MissingItem(dynamic item)
        {
            return new Difference() { Id = item.Id, SourceVer = item.Version, TargetVer = 0L };
        }

        private static Difference UnexpectedItem(dynamic item)
        {
            return new Difference() { Id = item.Id, SourceVer = 0L, TargetVer = item.Version };
        }
        #endregion

        #region Types / enums
        public class Difference
        {
            public int Id { get; set; }
            public long SourceVer { get; set; }
            public long TargetVer { get; set; }
            public bool TargetIsNewer { get { return TargetVer > SourceVer; } }
            public bool IsMissingInTarget { get { return TargetVer <= 0L && SourceVer > 0L; } }
            public bool IsUnknownToSource { get { return SourceVer <= 0L && TargetVer > 0L; } }
        }

        /// <summary>
        /// Enum to describe the equality of each id pair while walking
        /// two lists.  Named "The" for terseness and readability of 
        /// the switch statement using it.
        /// </summary>
        private enum The
        {
            TargetIsMissingId = -1,
            IdsMatch = 0,
            TargetHasUnexpectedId = 1
        }

        #endregion
    }
}

Program.cs

using System.Collections.Generic;

namespace Console
{
    class Program
    {
        public class Item
        {
            public int Id { get; set; }
            public int Version { get; set; }
        }

        static void Main(string[] args)
        {
            var d = new Differ();
            var s = new List<dynamic>();
            var t = new List<dynamic>();

            #region Populate lists
            s.Add(new Item() { Id = 1, Version = 1 });
            s.Add(new Item() { Id = 2, Version = 2 });
            s.Add(new Item() { Id = 3, Version = 1 });
            s.Add(new Item() { Id = 4, Version = 1 });
            s.Add(new Item() { Id = 6, Version = 1 });
            s.Add(new Item() { Id = 8, Version = 1 });
            s.Add(new Item() { Id = 10, Version = 1 });
            s.Add(new Item() { Id = 11, Version = 1 });
            s.Add(new Item() { Id = 14, Version = 1 });
            s.Add(new Item() { Id = 16, Version = 1 });

            t.Add(new Item() { Id = 1, Version = 1 });
            t.Add(new Item() { Id = 2, Version = 1 });
            t.Add(new Item() { Id = 4, Version = 1 });
            t.Add(new Item() { Id = 5, Version = 1 });
            t.Add(new Item() { Id = 6, Version = 2 });
            t.Add(new Item() { Id = 7, Version = 1 });
            t.Add(new Item() { Id = 9, Version = 1 });
            t.Add(new Item() { Id = 12, Version = 1 });
            t.Add(new Item() { Id = 13, Version = 1 });
            t.Add(new Item() { Id = 15, Version = 1 });

            #endregion

            foreach (var diff in d.IdentifyDifferences(s, t))
            {
                if (diff.IsMissingInTarget)
                    System.Console.WriteLine("MI: {0}", diff.Id);
                else if (diff.IsUnknownToSource)
                    System.Console.WriteLine("UI: {0}", diff.Id);
                else
                    System.Console.WriteLine("D: {0}, {1}", diff.Id, diff.SourceVer - diff.TargetVer);
            }

            System.Console.WriteLine();
            System.Console.WriteLine("Press enter.");
            System.Console.ReadLine();
        }
    }
}