How to perform merge sort using LINQ?

Question

Assume that you have two IEnumerbale objects. How we can merge them (in some condition e.g merge in merge sort ...) and create a unique IEnumerable? I tried this with Zip, but in Zip the two list sizes should be equal (maybe you didn't get exception but maybe we have some data lost.)

In addition, I try it by using Enumerable.Range(...).Select(...) but i didn't get an acceptable result.

Furthermore, my question is totally different from using Union or this one, in fact as I said like merge in merge sort I like to preserve lists order (in fact just want to fill some gaps in first list).

It's easy to handle it with for loop, but i can't see any full linq way.

Edit:

Sample input:

lst1 = {5,10,12}
lst2 = {7,9,16,20,25}

result: {5,7,9,10,12,16,20,25}

this can be done with a for loop and two pointer in O(n + m) but I'm looking for linq solution in O(n+m)

for loop solution:

        var lst1 = new List<int> { 5, 10, 12 };
        var lst2 = new List<int> { 7, 9, 16, 20, 25 };

        var result = new List<int>();

        int j = 0;
        for (int i = 0; i < lst1.Count; i++)
        {
            while (j < lst2.Count && lst2[j] < lst1[i])
            {
                result.Add(lst2[j]);
                j++;
            }
            result.Add(lst1[i]);
        }

        while (j < lst2.Count)
        {
            result.Add(lst2[j]);
            j++;
        }
        Console.WriteLine(string.Join(",", result.ToArray()));

Answer 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)

Answer 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();
      }
    }
  }
}

Answer 3

Use LINQ method Concat() http://msdn.microsoft.com/en-us/library/bb302894.aspx