Проблема реализации быстрой сортировки, массив отсортирован, но не выходит из условия рекурсивного разбиения

Question

Я реализовал алгоритм быстрой сортировки ниже, массив сортируется, но он не выходит из рекурсивного цикла. Может кто-нибудь проанализировать мой алгоритм быстрой сортировки ниже и проверить, что я делаю не так?

Пожалуйста, смотрите мой код ниже:

    package sort;

    import java.util.Arrays;

    public class QuickSort {

       public int array[];

       public void sort(int[] inputArr) {

           if (inputArr == null || inputArr.length == 0) {
               return;
           }
           this.array = inputArr;
           quickSort(0, this.array.length);
       }

        private void quickSort(int low, int high) 
         { 
             if (low < high) 
             {                  
                 int j = partition(low, high); 
                 quickSort(low, j); 
                 quickSort(j+1, high); 
             } 
         } 

       private int partition(int low, int high) { 
           int pivot = this.array[low];
           int i = low;
           int j = high;
           while (i<j) {
               do {
                   i++;
               } while (this.array[i] <= pivot);

               do {
                   j--;            
               } while (this.array[j] > pivot);
           }
           swap(low,j);
           return j;
       }

       private void swap(int i, int j) {
           int temp = this.array[i];
           this.array[i] = this.array[j];
           this.array[j] = temp;
       }

    }

Answer 1

Схема разбиения Hoare должна выглядеть следующим образом (используйте среднее значение для пивота):

       private int partition(int low, int high) { 
           int pivot = this.array[low+(high-low)/2];
           int i = low-1;
           int j = high+1;
           while (true) {
               while (this.array[++i] < pivot);   // not <=
               while (this.array[--j] > pivot);
               if(i >= j)
                   return j;
               swap(i,j);
           }
       }