Join two ordered sequences efficiently in C#

Question

Presume these two ordered sequences:

var outer = new char[] { 'a', 'b', 'b', 'c', 'd', 'd', 'e' };
var inner = new char[] { 'a', 'b', 'c', 'c', 'd', 'd' };

Knowing that elements from both sequences are ordered, how can they be inner-joined more efficiently than with Enumerable.Join to produce the following sequence of tuples?

{ 'a', 'a' }
{ 'b', 'b' }
{ 'b', 'b' }
{ 'c', 'c' }
{ 'c', 'c' }
{ 'd', 'd' }
{ 'd', 'd' }
{ 'd', 'd' }
{ 'd', 'd' }

Notice that, unlike with Enumerable.Intersect that produces only distinct elements from both sequences, the output sequence here returns tuples that represent every combination of elements from a one-to-one, one-to-many or many-to-many relationship.

The semantics are much the same as INNER JOIN in SQL Server. But, more specifically, I'm looking for a C# implementation with the performance characteristics of the merge join algorithm (INNER MERGE JOIN) that returns an IEnumerable with deferred execution.

The required method signature might look something like this:

IEnumerable<TResult> MergeJoin<TOuter, TInner, TKey, TResult>(
    this IEnumerable<TOuter> outer, 
    IEnumerable<TInner> inner, 
    Func<TOuter, TKey> outerKeySelector, 
    Func<TInner, TKey> innerKeySelector, 
    Func<TOuter, TInner, TResult> resultSelector)

Answer 1

MoreEnumerable.OrderedMerge from MoreLinq library does the job if both sequences are sorted.

https://github.com/morelinq/MoreLINQ

using MoreLinq;

IEnumerable<char> result = outer.OrderedMerge(innner);

Efficiency is good, compared to inner join. When N and M are the length of each sequence, Inner join makes a cartesian product so time is proportional to NxM OrderedMerge traverse each collection once so time is proportional to N+M

If the sequences are not sorted, the standard Linq Enumerable.OrderBy will do the job.

There are also some overloads:

// to provide a custom comparison criteria
public static IEnumerable<T> OrderedMerge<T>(this IEnumerable<T> first, IEnumerable<T> second, IComparer<T> comparer);

// to provide the key for comparisons
IEnumerable<T> OrderedMerge<T, TKey>(this IEnumerable<T> first, IEnumerable<T> second, Func<T, TKey> keySelector);

// + other overloads to select element to be merged when first element is less than second, 
// when second element is less than first 
// when first and second element are equal

Answer 2

I don't know of any existing Enumerable extension method that achieves this and no one should ever have to spend more time than I did to come up with this.

public static IEnumerable<TResult> MergeJoin<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector)
{
    if (outer == null)
        throw new ArgumentNullException(nameof(outer));

    if (inner == null)
        throw new ArgumentNullException(nameof(inner));

    if (outerKeySelector == null)
        throw new ArgumentNullException(nameof(outerKeySelector));

    if (innerKeySelector == null)
        throw new ArgumentNullException(nameof(innerKeySelector));

    if (resultSelector == null)
        throw new ArgumentNullException(nameof(resultSelector));

    return MergeJoinIterator(outer, inner, outerKeySelector, innerKeySelector, resultSelector, Comparer<TKey>.Default);
}

public static IEnumerable<TResult> MergeJoin<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IComparer<TKey> comparer)
{
    if (outer == null)
        throw new ArgumentNullException(nameof(outer));

    if (inner == null)
        throw new ArgumentNullException(nameof(inner));

    if (outerKeySelector == null)
        throw new ArgumentNullException(nameof(outerKeySelector));

    if (innerKeySelector == null)
        throw new ArgumentNullException(nameof(innerKeySelector));

    if (resultSelector == null)
        throw new ArgumentNullException(nameof(resultSelector));

    if (comparer == null)
        throw new ArgumentNullException(nameof(comparer));

    return MergeJoinIterator(outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
}

private static IEnumerable<TResult> MergeJoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IComparer<TKey> comparer)
{
    IEnumerator<TOuter> outerEnumerator = outer.GetEnumerator();

    if (!outerEnumerator.MoveNext())
        yield break;

    IEnumerator<TInner> innerEnumerator = inner.GetEnumerator();

    if (!innerEnumerator.MoveNext())
        yield break;

    TOuter outerElement = outerEnumerator.Current;
    TKey outerKey = outerKeySelector(outerElement);

    TInner innerElement = innerEnumerator.Current;
    TKey innerKey = innerKeySelector(innerElement);

    int comp = comparer.Compare(innerKey, outerKey);

    while (true)
    {
        if (comp < 0)
        {
            if (!innerEnumerator.MoveNext())
                break;

            innerElement = innerEnumerator.Current;
            innerKey = innerKeySelector(innerElement);
            comp = comparer.Compare(innerKey, outerKey);
            continue;
        }

        if (comp > 0)
        {
            if (!outerEnumerator.MoveNext())
                break;

            outerElement = outerEnumerator.Current;
            outerKey = outerKeySelector(outerElement);
            comp = comparer.Compare(innerKey, outerKey);
            continue;
        }

        yield return resultSelector(outerElement, innerElement);

        if (!outerEnumerator.MoveNext())
        {
            while (true)
            {
                if (!innerEnumerator.MoveNext())
                    break;

                innerElement = innerEnumerator.Current;
                innerKey = innerKeySelector(innerElement);
                comp = comparer.Compare(innerKey, outerKey);

                if (comp != 0)
                    break;

                yield return resultSelector(outerElement, innerElement);
            }

            break;
        }

        if (!innerEnumerator.MoveNext())
        {
            while (true)
            {
                outerElement = outerEnumerator.Current;
                outerKey = outerKeySelector(outerElement);
                comp = comparer.Compare(innerKey, outerKey);

                if (comp != 0)
                    break;

                yield return resultSelector(outerElement, innerElement);

                if (!outerEnumerator.MoveNext())
                    break;
            }

            break;
        }

        TOuter outerElementNext = outerEnumerator.Current;
        TKey outerKeyNext = outerKeySelector(outerElementNext);

        TInner innerElementNext = innerEnumerator.Current;
        TKey innerKeyNext = innerKeySelector(innerElementNext);

        comp = comparer.Compare(outerKeyNext, outerKey);
        bool stop = false;

        if (comp != 0)
        {
            comp = comparer.Compare(innerKeyNext, innerKey);

            if (comp == 0)
            {
                yield return resultSelector(outerElement, innerElementNext);

                while (true)
                {
                    if (!innerEnumerator.MoveNext())
                    {
                        stop = true;
                        break;
                    }

                    innerElementNext = innerEnumerator.Current;
                    innerKeyNext = innerKeySelector(innerElementNext);
                    comp = comparer.Compare(innerKeyNext, outerKey);

                    if (comp != 0)
                        break;

                    yield return resultSelector(outerElement, innerElementNext);
                }

                if (stop)
                    break;
            }

            outerElement = outerElementNext;
            outerKey = outerKeyNext;
            innerElement = innerElementNext;
            innerKey = innerKeyNext;
            comp = comparer.Compare(innerKey, outerKey);
            continue;
        }

        comp = comparer.Compare(innerKeyNext, innerKey);

        if (comp != 0)
        {
            yield return resultSelector(outerElementNext, innerElement);

            while (true)
            {
                if (!outerEnumerator.MoveNext())
                {
                    stop = true;
                    break;
                }

                outerElementNext = outerEnumerator.Current;
                outerKeyNext = outerKeySelector(outerElementNext);
                comp = comparer.Compare(innerKey, outerKeyNext);

                if (comp != 0)
                    break;

                yield return resultSelector(outerElementNext, innerElement);
            }

            if (stop)
                break;

            outerElement = outerElementNext;
            outerKey = outerKeyNext;
            innerElement = innerElementNext;
            innerKey = innerKeyNext;
            comp = comparer.Compare(innerKey, outerKey);
            continue;
        }

        yield return resultSelector(outerElement, innerElementNext);
        var innerRest = new List<TInner>();

        TInner innerElementFollowing = default(TInner);
        TKey innerKeyFollowing = default(TKey);

        while (true)
        {
            if (!innerEnumerator.MoveNext())
            {
                stop = true;
                break;
            }

            innerElementFollowing = innerEnumerator.Current;
            innerKeyFollowing = innerKeySelector(innerElementFollowing);
            comp = comparer.Compare(innerKeyFollowing, outerKey);

            if (comp != 0)
                break;

            yield return resultSelector(outerElement, innerElementFollowing);
            innerRest.Add(innerElementFollowing);
        }

        yield return resultSelector(outerElementNext, innerElement);
        yield return resultSelector(outerElementNext, innerElementNext);

        for (int i = 0; i < innerRest.Count; i++)
            yield return resultSelector(outerElementNext, innerRest[i]);

        while (true)
        {
            if (!outerEnumerator.MoveNext())
            {
                stop = true;
                break;
            }

            outerElementNext = outerEnumerator.Current;
            outerKeyNext = outerKeySelector(outerElementNext);
            comp = comparer.Compare(innerKey, outerKeyNext);

            if (comp != 0)
                break;

            yield return resultSelector(outerElementNext, innerElement);
            yield return resultSelector(outerElementNext, innerElementNext);

            for (int i = 0; i < innerRest.Count; i++)
                yield return resultSelector(outerElementNext, innerRest[i]);
        }

        if (stop)
            break;

        outerElement = outerElementNext;
        outerKey = outerKeyNext;
        innerElement = innerElementFollowing;
        innerKey = innerKeyFollowing;
        comp = comparer.Compare(innerKey, outerKey);
    }
}