title: Most efficient algorithm for merging sorted IEnumerable<T>
body: <p>I have several huge <strong>sorted enumerable sequences that I want to merge</strong>. Theses lists are manipulated as <code>IEnumerable</code> but are <em>already sorted</em>. Since input lists are sorted, it should be possible to merge them in one trip, without re-sorting anything.</p>
  
  <p>I would like to keep the defered execution behavior.</p>
  
  <p>I tried to write a naive algorithm which do that (see below). However, it looks pretty ugly and I'm sure it can be optimized. It may exist a more academical algorithm...</p>
  
  <pre><code>IEnumerable&lt;T&gt; MergeOrderedLists&lt;T, TOrder&gt;(IEnumerable&lt;IEnumerable&lt;T&gt;&gt; orderedlists, 
                                              Func&lt;T, TOrder&gt; orderBy)
  {
      var enumerators = orderedlists.ToDictionary(l =&gt; l.GetEnumerator(), l =&gt; default(T));
      IEnumerator&lt;T&gt; tag = null;
  
      var firstRun = true;
      while (true)
      {
          var toRemove = new List&lt;IEnumerator&lt;T&gt;&gt;();
          var toAdd = new List&lt;KeyValuePair&lt;IEnumerator&lt;T&gt;, T&gt;&gt;();
          foreach (var pair in enumerators.Where(pair =&gt; firstRun || tag == pair.Key))
          {
              if (pair.Key.MoveNext())
                  toAdd.Add(pair);
              else
                  toRemove.Add(pair.Key);
          }
  
          foreach (var enumerator in toRemove)
              enumerators.Remove(enumerator);
  
          foreach (var pair in toAdd)
              enumerators[pair.Key] = pair.Key.Current;
  
          if (enumerators.Count == 0)
              yield break;
  
          var min = enumerators.OrderBy(t =&gt; orderBy(t.Value)).FirstOrDefault();
          tag = min.Key;
          yield return min.Value;
  
          firstRun = false;
      }
  }
  </code></pre>
  
  <p>The method can be used like that:</p>
  
  <pre><code>// Person lists are already sorted by age
  MergeOrderedLists(orderedList, p =&gt; p.Age);
  </code></pre>
  
  <p>assuming the following <code>Person</code> class exists somewhere:</p>
  
  <pre><code>    public class Person
      {
          public int Age { get; set; }
      }
  </code></pre>
  
  <p>Duplicates should be conserved, we don't care about their order in the new sequence. Do you see any obvious optimization I could use?</p>