title: C# fastest union of 2 sets of sorted values
body: <p>What is the fastest way to union 2 sets of sorted values? Speed (big-O) is important here; not clarity - assume this is being done millions of times.</p>
  
  <p>Assume you do not know the type or range of the values, but have an efficent <code>IComparer&lt;T&gt;</code> and/or <code>IEqualityComparer&lt;T&gt;</code>.</p>
  
  <p>Given the following set of numbers:</p>
  
  <pre><code>var la = new int[] { 1, 2, 4, 5, 9 };
  var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };
  </code></pre>
  
  <p>I am expecting 1, 2, 3, 4, 5, 6, 7, 8, 9. The following stub may be used to test the code:</p>
  
  <pre><code>static void Main(string[] args)
  {
      var la = new int[] { 1, 2, 4, 5, 9 };
      var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };
  
      foreach (var item in UnionSorted(la, ra, Int32Comparer.Default))
      {
          Console.Write("{0}, ", item);
      }
      Console.ReadLine();
  }
  
  class Int32Comparer : IComparer&lt;Int32&gt;
  {
      public static readonly Int32Comparer Default = new Int32Comparer();
      public int Compare(int x, int y)
      {
          if (x &lt; y)
              return -1;
          else if (x &gt; y)
              return 1;
          else
              return 0;
      }
  }
  
  static IEnumerable&lt;T&gt; UnionSorted&lt;T&gt;(IEnumerable&lt;T&gt; sortedLeft, IEnumerable&lt;T&gt; sortedRight, IComparer&lt;T&gt; comparer)
  {
  }
  </code></pre>