title: time complexity for a sorting technique for stacks?
body: <p>Say I have the following pseudo code:</p>
  
  <pre><code>while A is not empty and stack top of A is less than x:
      pop A and push the returned value onto B
  push x onto A
  while B is not empty:
      pop B and push the returned valued onto A
  </code></pre>
  
  <blockquote>
    <p>say stacks A and B are initially empty. Insert n numbers with a new number x each time using the above algorithm, what would be worst time complexity.</p>
  </blockquote>
  
  <p>I was able to get that this algorithm would sort the inserting numbers with length <strong>n</strong> from smallest(top) to largest(bottom), and the best case would be <strong>n</strong> when the numbers inserted are already sorted, from largest to smallest. But I don't get how the worst case can be <strong>O(n^2)</strong>.</p>