title: C++ Quicksort array of string pointers
body: <p>I'm not sure what's wrong, but this isn't sorting right.</p>
  
  <p>This is the implementation:</p>
  
  <pre><code>int quickSort(std::string **arr, int left, int right)
  {
      static int swaps;
      int i = left, j = right;
      std::string *tmp;
      std::string pivot = *arr[(left + right) / 2]; //middle element
      //partition
      while( i &lt;= j ) {
          while ((*arr[i]).compare(pivot) &lt; 0) {
              i++;
          }
          while ((*arr[j]).compare(pivot) &lt; 0) {
              j--;
          }
          if ( i &lt;= j ) {
              swaps++;
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
          }
      }
      //recursion
      if ( left &lt; j ) {
          quickSort(arr, left, j);
      }
      if ( i &lt; right ) {
          quickSort(arr, i, right);
      }
      return swaps;
  }
  </code></pre>
  
  <p><code>arr</code> is an array of string pointers.  Each index points to a string, in this instance, the strings are all names.  The method is definitely making swaps, I just can't make any sense of what it's doing exactly.</p>
  
  <p>For example, given these initial values:</p>
  
  <pre><code>Pointer    Value
  0055B5D8 - JAMES
  0055B3F8 - JOHN
  0055C808 - ROBERT
  0055C8A8 - MICHAEL
  0055CB88 - WILLIAM
  0055CC28 - DAVID
  0055CCC8 - RICHARD
  0055CD68 - CHARLES
  0055CE08 - JOSEPH
  0055CEA8 - THOMAS
  </code></pre>
  
  <p>My <code>quickSort</code> method consistently moves them into this order:</p>
  
  <pre><code>Pointer    Value
  0055C8A8 - MICHAEL
  0055B5D8 - JAMES
  0055C808 - ROBERT
  0055B3F8 - JOHN
  0055CB88 - WILLIAM
  0055CEA8 - THOMAS
  0055CE08 - JOSEPH
  0055CD68 - CHARLES
  0055CCC8 - RICHARD
  0055CC28 - DAVID
  </code></pre>
  
  <p>The "unsorted" list has pointers in ascending order, given that I'm allocating all these one immediately after another to build the initial array.  But the "sorted" list doesn't seem sorted at all.</p>
  
  <p><strong>For clarity, the goal is to alphabetize the list of names.</strong></p>