Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to perform merge sort using LINQ?

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()));
like image 449
Saeed Amiri Avatar asked Dec 05 '22 19:12

Saeed Amiri


1 Answers

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)
like image 133
svick Avatar answered Dec 08 '22 11:12

svick