title: How to merge sorted sequences?
body: <p>Here’s a problem I’ve really been struggling with.  I need to merge two sorted sequences into a single sorted sequence.  Ideally, the algorithm should be lazy-evaluated, and not require caching more than one item from each sequence.  This is not a terribly difficult problem to solve, and I’ve been able to engineer a number of solutions in F#.  Unfortunately, every solution I’ve come up with has one of several problems.</p>
  
  <ol>
  <li><p>Recursive calls to subsequence generators using yield!.  This produces elegant looking solutions, but the creation of a subsequence for every item is a performance killer.</p></li>
  <li><p>Really arcane and unmaintainable code with deeply-stacked match switches, multiple nearly identical blocks of code, etc.</p></li>
  <li><p>Code which forces F# into a purely procedural mode (lots of mutable values, etc.).</p></li>
  </ol>
  
  <p>And all of the online examples I've been able to find founder on the same shoals.</p>
  
  <p>Am I missing something obvious: like it's either really simple or else obviously impossible?  Does anyone know of a really elegant solution that is also efficient and mostly functional?  (It doesn’t have to be purely functional.)  If not, I may end up caching subsequences and using lists or arrays.</p>