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:
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.
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.
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.