title: Skiena's Quick Sort implementation
body: <p>I find it hard to understand Skiena's quick sort.  Specifically, what he is doing with the <code>partition</code> function, especially the <code>firsthigh</code> parameter?</p>
  
  <pre><code>quicksort(item_type s[], int l, int h) {
      int p;                  /* index of partition */
      if ((h - l) &gt; 0) {
              p = partition(s, l, h);
              quicksort(s, l, p-1);
              quicksort(s, p+1, h);
      }
  }
  </code></pre>
  
  <blockquote>
    <p>We can partition the array in one linear scan for a particular pivot element by maintaining three sections of the array: less than the pivot (to the left of <code>firsthigh</code>), greater than or equal to the pivot (between <code>firsthigh</code> and <code>i</code>), and unexplored (to the right of <code>i</code>), as implemented below:</p>
  </blockquote>
  
  <pre><code>int partition(item_type s[], int l, int h) {
  ￼￼
      int i;           /* counter */
      int p;           /* pivot element index */
      int firsthigh;   /* divider position for pivot element */
  
      p = h;
      firsthigh = l;
      for (i = l; i  &lt;h; i++) {
          if (s[i] &lt; s[p]) {
              swap(&amp;s[i],&amp;s[firsthigh]);
              firsthigh ++;
          }
  
      swap(&amp;s[p],&amp;s[firsthigh]);
      return(firsthigh);
  }
  </code></pre>