title: quick sort implementation using stack
body: <p>I am reading a quick sort implementation using a stack at the following link.</p>
  
  <p><a href="http://codeidol.com/community/java/stack-size/11581/#part-3" rel="nofollow">link</a></p>
  
  <p>My question is regarding the following paragraph.</p>
  
  <blockquote>
    <p>The policy of putting the larger of the small subfiles on the stack
    ensures that each entry on the stack is no more than one-half of the
    size of the one below it, so that the stack needs to contain room for
    only about lg N entries. This maximum stack usage occurs when the
    partition always falls at the center of the file. For random files,
    the actual maximum stack size is much lower; for degenerate files it
    is likely to be small.</p>
    
    <p>This technique does not necessarily work in a truly recursive
    implementation, because it depends on end- or tail-recursion removal.
    If the last action of a procedure is to call another procedure, some
    programming environments will arrange things such that local variables
    are cleared from the stack before, rather than after, the call.
    Without end-recursion removal, we cannot guarantee that the stack size
    will be small for quicksort.</p>
  </blockquote>
  
  <ol>
  <li><p>What does the author mean by "that each entry on the stack is no more than one-half of the size of the one below it"? Could you please give an example of this.</p></li>
  <li><p>How did the author came to the conclusion that the stack needs space for only about <code>lg N</code> entries?</p></li>
  <li><p>What does authore mean by "Without end-recursion removal, we cannot guarantee that the stack size will be small for quicksort" ?</p></li>
  </ol>
  
  <p>Thanks for your time and help.</p>