title: Quicksort algorithm is nearly working but somehow elements near the center of the array are slightly unsorted
body: <p>I'm working on a recursive implementation of Quicksort, but I can't seem to get it correct. There is always some part of the array that somehow is out of order. Sometimes I sorts perfectly for smaller arrays but always when I test it on array size 100, the first few and last few indexes are sorted correctly, but the middle few aren't.</p>
  <p>Here is my Quicksort class</p>
  <pre><code>import java.util.Random;
  
  /**
   * Quicksort recursive implementation
   */
  public class Quicksort {
  
      private int[] arr;
  
      public Quicksort(int size) {
          arr = new int[size];
          autoFillArr(size);
      }
  
      public void autoFillArr(int size) {
          int counter = 0;
          while (counter &lt; size) {
              Random random = new Random();
              int randInt = random.nextInt(200) - 100;
              arr[counter] = randInt;
              counter++;
          }
      }
  
      public void quickSort() {
          quickSort(0, arr.length-1);
      }
  
      public void quickSort(int leftIndex, int rightIndex) {
          if (leftIndex &gt;= rightIndex) {
              return;
          }
          int pivot = (leftIndex + rightIndex)/2;
          int lEnd = partition(leftIndex, rightIndex, pivot);
          quickSort(leftIndex, lEnd-1);
          quickSort(lEnd, rightIndex);
      }
  
      /**
       * @return  The position of the left point.
       */
      public int partition(int leftIndex, int rightIndex, int pivot) {
          while (leftIndex &lt;= rightIndex) {
              while (arr[leftIndex] &lt; arr[pivot]) {
                  leftIndex++;
              }
              while (arr[rightIndex] &gt; arr[pivot]) {
                  rightIndex--;
              }
              if (leftIndex &lt;= rightIndex) {
                  swap(leftIndex, rightIndex);
                  leftIndex++;
                  rightIndex--;
              }
          }
          return leftIndex;
      }
  
      /**
       * Swaps the element at position leftIndex with the element at position
       * rightIndex.
       */
      public void swap(int leftIndex, int rightIndex) {
          int temp = arr[leftIndex];
          arr[leftIndex] = arr[rightIndex];
          arr[rightIndex] = temp;
      }
  
      public int[] getArr() {
          return arr;
      }
  }
  </code></pre>