DiffSortedSequences.cs

public static class Extensions
{
        public static void DiffSortedSequences<T>(
            this IReadOnlyList<T> left,
            IReadOnlyList<T> right,
            IComparer<T> comparer,
            Action<T> added = null,
            Action<T> removed = null,
            Action<T> same = null)
        {
            left ??= Array.Empty<T>();
            right ??= Array.Empty<T>();

            for (int l = 0, r = 0; l < left.Count || r < right.Count; )
            {
                if (l >= left.Count)
                {
                    added?.Invoke(right[r]);
                    r++;
                    continue;
                }
                else if (r >= right.Count)
                {
                    removed?.Invoke(left[l]);
                    l++;
                    continue;
                }

                var leftItem = left[l];
                var rightItem = right[r];

                int comparison = comparer.Compare(leftItem, rightItem);
                if (comparison < 0)
                {
                    removed?.Invoke(leftItem);
                    l++;
                }
                else if (comparison > 0)
                {
                    added?.Invoke(rightItem);
                    r++;
                }
                else
                {
                    same?.Invoke(leftItem);
                    l++;
                    r++;
                }
            }
        }
}

Test.cs

    public class CollectionTests
    {
        class Comparer : Comparer<char>
        {
            public static Comparer Instance { get; } = new Comparer();

            public override int Compare(char x, char y)
            {
                return x.CompareTo(y);
            }
        }

        [Fact]
        public void SortedDiff1()
        {
            Test("123", "123", "", "");
            Test("123", "23", "", "1");
            Test("123", "3", "", "12");
            Test("123", "2", "", "13");
            Test("123", "", "", "123");
            Test("12", "123", "3", "");
            Test("2", "123", "13", "");
            Test("23", "123", "1", "");
            Test("", "123", "123", "");
            Test("123", "", "", "123");
        }

        private void Test(string left, string right, string expectedAdded, string expectedRemoved)
        {
            List<char> actualRemoved = new();
            List<char> actualAdded = new();

            ICollectionExtensions.DiffSortedSequences(
                left.ToCharArray(),
                right.ToCharArray(),
                Comparer.Instance,
                actualAdded.Add,
                actualRemoved.Add);

            Assert.Equal(expectedRemoved, actualRemoved);
            Assert.Equal(expectedAdded, actualAdded);
        }
    }