Introduction

Merging sorted IEnumerable<T> sequences efficiently depends on how many sequences you have and whether you want eager materialization or lazy streaming. For two sorted sequences, a standard merge walk is optimal. For many sorted sequences, the usual best approach is a min-heap or priority queue so you only ever compare the current head item from each input.

Two Sorted Sequences: Classic Merge

If you only have two already sorted inputs, the classic merge step from merge sort is optimal. It runs in linear time relative to the total number of items.

1using System;
2using System.Collections.Generic;
3
4public static class MergeUtil
5{
6    public static IEnumerable<T> MergeTwo<T>(
7        IEnumerable<T> first,
8        IEnumerable<T> second,
9        IComparer<T>? comparer = null)
10    {
11        comparer ??= Comparer<T>.Default;
12
13        using var e1 = first.GetEnumerator();
14        using var e2 = second.GetEnumerator();
15
16        bool has1 = e1.MoveNext();
17        bool has2 = e2.MoveNext();
18
19        while (has1 && has2)
20        {
21            if (comparer.Compare(e1.Current, e2.Current) <= 0)
22            {
23                yield return e1.Current;
24                has1 = e1.MoveNext();
25            }
26            else
27            {
28                yield return e2.Current;
29                has2 = e2.MoveNext();
30            }
31        }
32
33        while (has1)
34        {
35            yield return e1.Current;
36            has1 = e1.MoveNext();
37        }
38
39        while (has2)
40        {
41            yield return e2.Current;
42            has2 = e2.MoveNext();
43        }
44    }
45}

This is O(n + m) for two sequences of sizes n and m.

Many Sorted Sequences: Use a Priority Queue

If you need to merge k sorted sequences, repeatedly scanning all current heads is wasteful. A priority queue keeps the smallest current element at the top.

Time complexity becomes roughly O(N log k), where N is the total number of items across all sequences.

1using System;
2using System.Collections.Generic;
3
4public static class MultiMerge
5{
6    private sealed class Entry<T>
7    {
8        public required T Value { get; init; }
9        public required IEnumerator<T> Enumerator { get; init; }
10    }
11
12    public static IEnumerable<T> MergeMany<T>(
13        IEnumerable<IEnumerable<T>> sources,
14        IComparer<T>? comparer = null)
15    {
16        comparer ??= Comparer<T>.Default;
17        var queue = new PriorityQueue<Entry<T>, T>(comparer);
18        var enumerators = new List<IEnumerator<T>>();
19
20        try
21        {
22            foreach (var source in sources)
23            {
24                var e = source.GetEnumerator();
25                enumerators.Add(e);
26                if (e.MoveNext())
27                {
28                    queue.Enqueue(new Entry<T> { Value = e.Current, Enumerator = e }, e.Current);
29                }
30            }
31
32            while (queue.Count > 0)
33            {
34                var entry = queue.Dequeue();
35                yield return entry.Value;
36
37                if (entry.Enumerator.MoveNext())
38                {
39                    queue.Enqueue(
40                        new Entry<T> { Value = entry.Enumerator.Current, Enumerator = entry.Enumerator },
41                        entry.Enumerator.Current);
42                }
43            }
44        }
45        finally
46        {
47            foreach (var e in enumerators)
48            {
49                e.Dispose();
50            }
51        }
52    }
53}

This keeps the merge lazy and memory-efficient.

Why Concat().OrderBy() Is Usually Worse

A common naive answer is:

var merged = seq1.Concat(seq2).OrderBy(x => x);

That works, but it throws away the fact that the inputs are already sorted. It typically costs O(N log N) instead of linear merge cost for two inputs or O(N log k) for many inputs.

It also usually buffers more data before producing output.

IEnumerable<T> and Laziness Matter

One advantage of a proper merge iterator is that it can stream results. That matters when:

• Inputs are large.
• Inputs are generated lazily.
• You want to stop consuming early.

A yield-based merge can start returning values immediately, while a sort-based approach often needs more materialization first.

Handling Custom Ordering

Do not assume default comparison always matches domain rules. Accept an IComparer<T> when the sort order is custom.

Example:

var comparer = Comparer<string>.Create((a, b) => StringComparer.OrdinalIgnoreCase.Compare(a, b));

If the merge comparer does not match the comparer used to sort the input sequences, the result may not stay globally sorted.

When Inputs Are Not Actually Sorted

All of these algorithms assume each input sequence is already sorted according to the same ordering. If that assumption is false, merge algorithms will produce incorrect results without warning.

When correctness matters, validate the invariant in tests or keep the merge API narrow enough that callers cannot misuse it casually.

Common Pitfalls

• Using Concat().OrderBy() even though inputs are already sorted.
• Forgetting that the comparer must match the ordering of all input sequences.
• Writing a many-sequence merge by scanning every head item repeatedly.
• Materializing entire sequences when a lazy iterator would be enough.
• Ignoring enumerator disposal in custom iterator implementations.

Summary

• For two sorted sequences, the classic merge walk is optimal and linear.
• For many sorted sequences, a priority queue gives the best general-purpose performance.
• Proper merge logic preserves laziness and avoids unnecessary buffering.
• 'Concat().OrderBy() is usually simpler but less efficient for already sorted inputs.'
• Correctness depends on every input sequence being sorted under the same comparer.