 <p>I don't know of an existing algorithm that's really suited to this task. The obvious alternative is to write roughly the code above, but as a generic algorithm:</p> <pre><code>template &lt;class InIter1, class InIter2, class OutIter&gt; OutIter unsorted_merge(InIter1 b1, Inter1 e1, inIter2 b2, OutIter r) { while (b1 != e1) { *r = *b1; ++r; ++b1; *r = *b2; ++r; ++b2; } return r; }; </code></pre> <p>Even though <em>that</em> code may not be particularly elegant or beautiful, the rest of the code can be:</p> <pre><code>unsorted_merge(p.begin(), p.end(), q.begin(), std::back_inserter(pq)); </code></pre>