title: Java quick sort returns partially sorted list
body: <p>My program (a decryptor that uses letter frequencies to decrypt things) has two ArrayLists that it uses to keeps track of letter frequencies. I paired these ArrayLists so that one (the list of characters in the input) was always linked to the other (the list of frequencies in the input) so that the character at index i in one would always correspond to the the frequency at index i in the other. I used a quicksort algorithm to sort in descending order. Here is the code for the quicksort and swap methods: </p>
  
  <pre><code>private static void quickSort(int low, int high){
  
  
      int i = low;
      int j = high;
      long middle = freqInCiphertext.get((low+high)/2);
  
      while (i &lt; j) {
          while (freqInCiphertext.get(i) &gt; middle) {
              i++;
          } //End while
          while (freqInCiphertext.get(j) &lt; middle) {
              j--;
          }//End while
          if (j &gt;= i) {
              swap(i, j);
              i++;
              j--;
          } // End if
      } // End while
  
  
      if (low&lt;j) {
          quickSort(low, j);
      } else if (i&lt;high) {
          quickSort(i, high);
      } //end if
  }//End quickSort
  
  private static void swap(int i, int j) {
  int tempInt = freqInCiphertext.get(i);
  String tempString = charsInCiphertext.get(i);
  
  freqInCiphertext.set(i, freqInCiphertext.get(j));
  charsInCiphertext.set(i, charsInCiphertext.get(j));
  
  freqInCiphertext.set(j, tempInt);
  charsInCiphertext.set(j, tempString);
  }// End swap
  </code></pre>
  
  <p>However, when I run my code, it returns the array lists partially sorted, like this:</p>
  
  <pre><code>[ , e, t, a, o, n, i, h, r, d, l, u, s, m, z, q, x, j, v, k, p, f, w, c, b, y, g]
  [64031, 25856, 19326, 17571, 16398, 14349, 14200, 12784, 11617, 9930, 8391, 5820, 12934, 5636, 173, 178, 312, 356, 1929, 2175, 3186, 4310, 5479, 4666, 3491, 4673, 5100]
  </code></pre>
  
  <p>Can anybody see any errors in the algoritm? I have tried it a couple of different ways already (like a >= instead of a >, etc.) without luck.</p>