title: Difference of the two versions of partition used in quicksort
body: <p>The first one is straightforward, just walk from both sides until finding a reversion.</p>
  
  <pre><code>/*C++ version, [first, last), last needs --first to fetch the last element*/
  /*returns the middle of partitioning result*/
  int* partition( int *first, int *last, int pivot ) {
      while (true) {
          while (*first &lt; pivot) ++first;
          --last;//Don't edit this, it's true.
          while (pivot &lt; *last) --last;
          if (!(first &lt; last)) return first;
          swap(*first, *last);
          ++first;
      }
  }
  </code></pre>
  
  <p>The second one (shown in "<em>Introduction to algorithms</em>") is:</p>
  
  <pre><code>int* partition( int a[], int n, int pivot ) {
      bound = 0;
      for ( i = 1; i != n; ++i )
          if ( a[i] &lt; pivot )
              swap( &amp;a[i], &amp;a[++bound]);
      swap(a, a + bound);
      return a + bound;
  }
  </code></pre>
  
  <p>The invariant of the second one is " <strong>All elements before bound is less than pivot</strong> " .</p>
  
  <p><strong>Q: And what is the advantages and disadvantages of the two versions?</strong></p>
  
  <p>I'll give one first, the second one require ++ operation on the iterator( pointer ), so it can be applied to some <code>ForwardIterator</code> like the iterator of a linked list. Other tips?</p>