8

Given

IEnumerable<T> first;
IEnumerable<T> second;

and that both first and second are ordered by a comparer Func<T, T, int> that returns 0 for equality, -1 when the first is "smaller" and 1 when the second is "smaller".

Is there a straight-forward way using LINQ to merge the two sequences in a way that makes the resulting sequence also ordered by the same comparer?

We're currently using a hand-crafted algorithm that works, but the readability of a straight-forward LINQ statement would be preferable.

Johann Gerell
  • 24,991
  • 10
  • 72
  • 122
  • 2
    possible duplicate of [Most efficient algorithm for merging sorted IEnumerable](http://stackoverflow.com/questions/2767007/most-efficient-algorithm-for-merging-sorted-ienumerablet) – Jon Mar 21 '12 at 15:34
  • Have you extracted your hand-crafted algorithm into a separate method? That would be the simplest way to improve readability. – phoog Mar 21 '12 at 15:42
  • 2
    If you like readability (over performance) then: `var both = first.Union(second).OrderBy(comparer);` – George Duckett Mar 21 '12 at 15:43
  • @Jon: I already know about that "the most efficient algorithm" thread. Was just hoping that LINQ would help with readability. :) – Johann Gerell Mar 21 '12 at 15:48
  • 2
    @GeorgeDuckett: That method will discard duplicates (probably not desired). `var both = first.Concat(second).OrderBy(comparer);` is probably what you want. – Ron Warholic Mar 21 '12 at 16:06
  • @JohannGerell: Sure, that was not my point. The point was to show you that such a method has already been written, so you can copy/paste the extension method and go. Also, to prevent people from scattering identical answers across separate questions. – Jon Mar 21 '12 at 16:20
  • The problem here is that, even though there is an IOrderedEnumerable interface defined in System.Linq, it doesn't expose the IComparer used to sort the the two Enumerables. without being able to compare the IComparers (and their settings), you can't assume both Enumerables are in the same order. Which is probably why things are the way they are. `.Concat/.Union` followed by `.OrderBy/.OrderByDescending` is the best Linq can give you. – jessehouwing Mar 21 '12 at 18:48
  • See http://stackoverflow.com/a/14444706/184528 – cdiggins Jan 21 '13 at 18:34
  • I was not happy with the previous answers, so I posted mine [here](https://stackoverflow.com/a/76363717/21984976). – m-ringler May 30 '23 at 10:38

2 Answers2

14

You could define an extension method for this. Something like

public static IEnumerable<T> MergeSorted<T>(this IEnumerable<T> first, IEnumerable<T> second, Func<T, T, int> comparer) 
{
    using (var firstEnumerator = first.GetEnumerator())
    using (var secondEnumerator = second.GetEnumerator())
    {

        var elementsLeftInFirst = firstEnumerator.MoveNext();
        var elementsLeftInSecond = secondEnumerator.MoveNext();
        while (elementsLeftInFirst || elementsLeftInSecond)
        {
            if (!elementsLeftInFirst)
            {
                    do
                    {
                        yield return secondEnumerator.Current;
                    } while (secondEnumerator.MoveNext());
                    yield break;
            }

            if (!elementsLeftInSecond)
            {
                    do
                    {
                        yield return firstEnumerator.Current;
                    } while (firstEnumerator.MoveNext());
                    yield break;
            }

            if (comparer(firstEnumerator.Current, secondEnumerator.Current) < 0)
            {
                yield return firstEnumerator.Current;
                elementsLeftInFirst = firstEnumerator.MoveNext();
            }
            else
            {
                yield return secondEnumerator.Current;
                elementsLeftInSecond = secondEnumerator.MoveNext();
            }
        }
    }
}

Usage:

var s1 = new[] { 1, 3, 5, 7, 9 };
var s2 = new[] { 2, 4, 6, 6, 6, 8 };

var merged = s1.MergeSorted(s2, (a, b) => a > b ? 1 : -1).ToList();

Console.WriteLine(string.Join(", ", merged));

Output:

1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9
Brian Rasmussen
  • 114,645
  • 34
  • 221
  • 317
  • Parameter `comparer` could be allowed to be null (optional parameter) and set to `Comparer.Default.Compare` if it is null. – springy76 Nov 06 '14 at 18:29
0

I think, converting the first enumerable to list and adding second item to this list then calling sort will do the trick.

        IEnumerable<int> first = new List<int>(){1,3};
        IEnumerable<int> second = new List<int>(){2,4};

        var temp = first.ToList();
        temp.AddRange(second);


        temp.Sort(new Comparison<int>(comparer)); // where comparer is Func<T,T,int>
daryal
  • 14,643
  • 4
  • 38
  • 54
  • 9
    This implementation is O(n) in extra storage, O(n lg n) in time typical case and O(n^2) in time worst case. There is an algorithm which is both O(1) in extra storage and O(n) in time. – Eric Lippert Mar 21 '12 at 16:20