title: Sorting a Stack in Ascending Order?
body: <p>What is the best method for <strong>sorting a stack in ascending order? I</strong> came across this interview question, and I was running into some problems for the best and most efficient solution.</p>
  
  <p>There are two methods that I can think of.</p>
  
  <ol>
  <li><p>To pop all the contents of the stack and store them in an array, and then sort the array in<br>
  <code>O(nLog n)</code> and then push the contents back the stack. Not the best way....</p></li>
  <li><p>Do the recursive implementation of the stack for sorting it </p></li>
  </ol>
  
  
  
  <pre><code>void sort(stack)
  {
      type x;
  
      if (!isEmpty(stack)) {
          x = pop(stack);
          sort(stack);
          insert(x, stack);
      }           
  }
  
  void insert(x, stack)
  {
      type y;
  
      if (!isEmpty(stack) &amp;&amp; top(stack) &lt; x) {
          y = pop(stack);
          insert(x, stack);
          push(y, stack);
      } 
      else {
          push(x, stack);
      }
  } 
  </code></pre>
  
  <p>But the 2nd method seems to be making too many recursive calls and the overhead will be a problem if the stack happens to be really big.</p>
  
  <p>Is it possible to solve this problem in a much better way for the best space and time complexity? </p>
  
  <p>There are so many recursive calls, (overlapping subproblems), is this a contender for <code>dynamic programming</code> type of problems?</p>
  
  <p>What would be the best way to solve this? ?</p>