C# fastest union of 2 sets of sorted values

Question

What is the fastest way to union 2 sets of sorted values? Speed (big-O) is important here; not clarity - assume this is being done millions of times.

Assume you do not know the type or range of the values, but have an efficent IComparer<T> and/or IEqualityComparer<T>.

Given the following set of numbers:

var la = new int[] { 1, 2, 4, 5, 9 };
var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

I am expecting 1, 2, 3, 4, 5, 6, 7, 8, 9. The following stub may be used to test the code:

static void Main(string[] args)
{
    var la = new int[] { 1, 2, 4, 5, 9 };
    var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

    foreach (var item in UnionSorted(la, ra, Int32Comparer.Default))
    {
        Console.Write("{0}, ", item);
    }
    Console.ReadLine();
}

class Int32Comparer : IComparer<Int32>
{
    public static readonly Int32Comparer Default = new Int32Comparer();
    public int Compare(int x, int y)
    {
        if (x < y)
            return -1;
        else if (x > y)
            return 1;
        else
            return 0;
    }
}

static IEnumerable<T> UnionSorted<T>(IEnumerable<T> sortedLeft, IEnumerable<T> sortedRight, IComparer<T> comparer)
{
}

Answer 1

The following method returns the correct results:

static IEnumerable<T> UnionSorted<T>(IEnumerable<T> sortedLeft, IEnumerable<T> sortedRight, IComparer<T> comparer)
{
    var first = true;

    var continueLeft = true;
    var continueRight = true;

    T left = default(T);
    T right = default(T);

    using (var el = sortedLeft.GetEnumerator())
    using (var er = sortedRight.GetEnumerator())
    {
        // Loop until both enumeration are done.
        while (continueLeft | continueRight)
        {
            // Only if both enumerations have values.
            if (continueLeft & continueRight)
            {
                    // Seed the enumeration.
                    if (first)
                    {
                        continueLeft = el.MoveNext();
                        if (continueLeft)
                        {
                            left = el.Current;
                        }
                        else 
                        {
                            // left is empty, just dump the right enumerable
                            while (er.MoveNext())
                                yield return er.Current;
                            yield break;
                        }

                        continueRight = er.MoveNext();
                        if (continueRight)
                        {
                            right = er.Current;
                        }
                        else
                        {
                            // right is empty, just dump the left enumerable
                            if (continueLeft)
                            {
                                // there was a value when it was read earlier, let's return it before continuing
                                do
                                {
                                    yield return el.Current;
                                }
                                while (el.MoveNext());
                            } // if continueLeft is false, then both enumerable are empty here.
                            yield break;
                        }

                        first = false;
                    }

                // Compare them and decide which to return.
                var comp = comparer.Compare(left, right);
                if (comp < 0)
                {
                    yield return left;
                    // We only advance left until they match.
                    continueLeft = el.MoveNext();
                    if (continueLeft)
                        left = el.Current;
                }
                else if (comp > 0)
                {
                    yield return right;
                    continueRight = er.MoveNext();
                    if (continueRight)
                        right = er.Current;
                }
                else
                {
                    // The both match, so advance both.
                    yield return left;
                    continueLeft = el.MoveNext();
                    if (continueLeft)
                        left = el.Current;
                    continueRight = er.MoveNext();
                    if (continueRight)
                        right = er.Current;
                }
            }
            // One of the lists is done, don't advance it.
            else if (continueLeft)
            {
                yield return left;
                continueLeft = el.MoveNext();
                if (continueLeft)
                    left = el.Current;
            }
            else if (continueRight)
            {
                yield return right;
                continueRight = er.MoveNext();
                if (continueRight)
                    right = er.Current;
            }
        }
    }
}

The space is ~O(6) and time ~O(max(n,m)) (where m is the second set).

Answer 2

I'm going to give LINQ the benefit of the doubt and say this is probably as fast as you are going to get without writing excessive code:

var result = la.Union(ra);

EDITED: Thanks, I missed the sorted part.

You could do:

var result = la.Union(ra).OrderBy(i => i);

Answer 3

This will make your UnionSorted function a little less versatile, but you can make a small improvement by making an assumption about types. If you do the comparison inside the loop itself (rather than calling the Int32Comparer) then that'll save on some function call overhead.

So your UnionSorted declaration becomes this...

static IEnumerable<int> UnionSorted(IEnumerable<int> sortedLeft, IEnumerable<int> sortedRight)

And then you do this inside the loop, getting rid of the call to comparer.Compare()...

//var comp = comparer.Compare(left, right); // too slow

int comp = 0;
if (left < right)
    comp = -1;
else if (left > right)
    comp = 1;

In my testing this was about 15% faster.

Answer 4

I would solve the problem this way. (I am making an assumption which lightens the difficulty of this problem significantly, only to illustrate the idea.)

Assumption: All numbers contained in sets are non-negative.

Create a word of at least n bits, where n is the largest value you expect. (If the largest value you expect is 12, then you must create a word of 16 bits.).

Iterate through both sets. For each value, val, or the val-th bit with 1.

Once done, count the amount of bits set to 1. Create an array of that size. Go through each bit one by one, adding n to the new array if the n-th bit is set.