Adding SortedMerge to Elevate

One of the reasons I love CodeMash is because I great questions from very smart people. This last CodeMash, one of questions was:

Is there a way to merge two sequences into a new sorted sequence, assuming that both source sequences are already sorted.

There is an obvious simple answer using LINQ:

sequence1.Concat(sequence2).OrderBy(n => n)

That obvious answer works, but it is sadly slower than it needs to be. A faster solution would make use of the fact that the input sequences are already sorted. In fact, this is much slower because the Concat() call puts the the two sequences in an order that makes OrderBy do more work.

          public
          static IEnumerable<T> sortedMerge<T>(
    IEnumerable<T> sequence1, 
    IEnumerable<T> sequence2, 
    IComparer<T> comparer)
{
    var iter1 = sequence1.GetEnumerator();
    var iter2 = sequence2.GetEnumerator();
          bool seq2 = iter2.MoveNext();
          bool seq1 = iter1.MoveNext();
 
          while (seq1 && seq2)
    {
          if (comparer.Compare(iter1.Current, iter2.Current) <= 0)
        {
          yield
          return iter1.Current;
            seq1 = iter1.MoveNext();
        } else
        {
          yield
          return iter2.Current;
            seq2 = iter2.MoveNext();
        }
    }
          // might have some items in one of the sequences
        
          // remaining.
        
          while (seq1)
    {
          yield
          return iter1.Current;
        seq1 = iter1.MoveNext();
    }
          while (seq2)
    {
          yield
          return iter2.Current;
        seq2 = iter2.MoveNext();
    }
}
 
          public
          static IEnumerable<T> SortedMerge<T>(
    IEnumerable<T> sequence1, 
    IEnumerable<T> sequence2)
          where T : IComparable<T>
{
    var comparer = Comparer<T>.Default;
          return sortedMerge(sequence1, sequence2, comparer);
}

It’s just a bit more LINQ work: Keep returning the next item in each sequence while it is less than the next item in the other sequence. The two overloads allow you to merge sequences that are sorted either using the type’s IComparable interface or a customer IComparer.

I wrote this using a TDD approach, ensuring that my version agreed with the original LINQ query. You can get the code and the tests from Elevate.

Created: 1/26/2011 4:11:06 AM

Current Projects

I create content for .NET Core. My work appears in the .NET Core documentation site. I'm primarily responsible for the section that will help you learn C#.

All of these projects are Open Source (using the Creative Commons license for content, and the MIT license for code). If you would like to contribute, visit our GitHub Repository. Or, if you have questions, comments, or ideas for improvement, please create an issue for us.

I'm also the president of Humanitarian Toolbox. We build Open Source software that supports Humanitarian Disaster Relief efforts. We'd appreciate any help you can give to our projects. Look at our GitHub home page to see a list of our current projects. See what interests you, and dive in.

Or, if you have a group of volunteers, talk to us about hosting a codeathon event.