title: merging a queue with elements in ascending order and a stack with elements in descending order
body: <p>Suppose I have a queue with elements in ascending order, i.e. head &lt; 2nd &lt; 3rd &lt; ... &lt; tail</p>
  
  <p>and a stack with elements in descending order, i.e. top > 2nd > 3rd > ...</p>
  
  <p>and their size differ at most 1 (they could be of same size).</p>
  
  <p>What is the most efficient way of merging them together into the same queue (or stack) as a single sorted sequence without additional stack/queue?</p>
  
  <p>It seems that the best I thought of so far is a quadratic algorithm that is basically selection sort, and it doesn't really take advantage of the fact that the queue and the stack are pre-sorted and their size. I am wondering if we can do better?</p>