QuickSort, используя медианную точку. Не правильно Сортировка

Question

Я пытаюсь создать свой собственный метод quickSort и помещаю опорную точку в медианное значение среди первого, среднего и последнего элементов списка. Однако, когда я помещаю некоторые случайные числа в массив, а затем использую метод quickSort, они иногда не сортируются правильно. Мне было интересно, что такое ошибка в моем коде и как я могу это исправить.

public static <T extends Comparable<T>> void quickSort(T[] list) { 
     quickSort(list, 0, list.length-1); 
} 

public static <T extends Comparable<T>> void quickSort(T[] list, int first, int last) { 
     int pivotIndex=0; 
     if(last>first) { 
      pivotIndex=partition(list,first,last, smartPivot); 
      quickSort(list, first, pivotIndex-1, smartPivot); 
      quickSort(list,pivotIndex+1, last, smartPivot); 
     } 
    } 
    public static <T extends Comparable<T>> void swap(T[] list, int index, int index2) { 
     T temp=list[index]; 
     list[index]=list[index2]; 
     list[index2]=temp; 
} 

public static <T extends Comparable<T>> T median(T[] list, int first, int last) { 
     int pivotIndex=(first+last)/2; 
     if (list[last].compareTo(list[first])<0) { 
      swap(list,first,last); 
     } 

     else if(list[last].compareTo(list[pivotIndex])<0) { 
      swap(list,pivotIndex,last); 
     } 

     else if (list[pivotIndex].compareTo(list[first])<0) { 
      swap(list,first,pivotIndex); 
     } 

     swap(list,pivotIndex, last-1); 
     return list[last-1]; 
} 

public static <T extends Comparable<T>> int partition(T[] list, int first, int last) { 


     T pivot=null; 
     int low=first+1; 
     int high=last; 

     pivot=median(list,first,last); 
      while(high>low) { 
       while(low<=high && list[low].compareTo(pivot)<=0) { 
        low++; 
       } 
       while(low<=high && list[high].compareTo(pivot)>0) { 
        high--; 
       } 

       if(high>low) { 
        swap(list,high,low); 
       } 
      } 

      while(high>first && list[high].compareTo(pivot)>=0) { 
       high--; 
      } 
      return first; 
     } 

    public static void main(String[] args) { 

     Integer[] x={34,34543,98,562,1,6456,0,9}; 

     quickSort(x,0,x.length-1); 
     for(int j=0; j<x.length;j++) { 
      System.out.print(x[j]+" "); 
     } 

}

Answer 1

partition, кажется, предполагает, что median будет двигаться стержень в передней части списка (low=first+1), но это на самом деле перемещает его к не совсем конец списка.