How to perform merge sort using LINQ?

Solution 1:

There is no such method in LINQ. And I don't think it's possible to combine the existing methods to do exactly what you want (if it was, it would be overly complicated).

But implementing such method yourself isn't that hard:

static IEnumerable<T> Merge<T>(this IEnumerable<T> first,
                               IEnumerable<T> second,
                               Func<T, T, bool> predicate)
{
    // validation ommited

    using (var firstEnumerator = first.GetEnumerator())
    using (var secondEnumerator = second.GetEnumerator())
    {
        bool firstCond = firstEnumerator.MoveNext();
        bool secondCond = secondEnumerator.MoveNext();

        while (firstCond && secondCond)
        {
            if (predicate(firstEnumerator.Current,  secondEnumerator.Current))
            {
                yield return firstEnumerator.Current;
                firstCond = firstEnumerator.MoveNext();
            }
            else
            {
                yield return secondEnumerator.Current;
                secondCond = secondEnumerator.MoveNext();
            }
        }

        while (firstCond)
        {
            yield return firstEnumerator.Current;
            firstCond = firstEnumerator.MoveNext();
        }

        while (secondCond)
        {
            yield return secondEnumerator.Current;
            secondCond = secondEnumerator.MoveNext();
        }
    }
}

And you could use it like this:

lst1.Merge(lst2, (i, j) => i < j)

Solution 2:

There is no Merge method in System.Linq.Enumerable. If you want one, you have to write it (with a for loop and a yield statement).

As with many "just by linq" questions - you should assume that every linq method is backed by some plain old .NET code that you could have written yourself.

Here's an untested freehand non-generic implementation

public static IEnumerable<int> Merge
(
this IEnumerable<int> source1,
IEnumerable<int> source2
)
{
  using(Enumerator<int> e1 = source1.GetEnumerator())
  {
    bool more1 = e1.MoveNext();
    using(Enumerator<int> e2 = source2.GetEnumerator()
    {
      bool more2 = e2.MoveNext();

      while (more1 && more2)
      {
        int v1 = e1.Current;
        int v2 = e2.Current;
        if (v1 < v2)
        {
          yield return v1;
          more1 = e1.MoveNext();
        }
        else
        {
          yield return v2;
          more2 = e2.MoveNext();
        }

      }
      while (more1 && ! more2)
      {
        yield return e1.Current;
        more1 = e1.MoveNext();
      }
      while (more2 && ! more1)
      {
        yield return e2.Current;
        more2 = e2.MoveNext();
      }
    }
  }
}