Dual Pivot QuickSort

Question

Итак, я работаю над проблемой, которая реализует QuickSort с тремя разделами, выбирая самый левый и самый правый элемент массива в качестве опорных точек. Моя функция в основном делает разделение lomoto слева и справа от массива. Алгоритм в основном сортирует массив в 95% случаев, однако есть пара, для которой он не работает. Кто-нибудь знает почему?

public static int[] partition2Pivots(int[] arr, int p, int r) {

    if(arr[p]>arr[r]) {
        int temp = arr[p];
        arr[p] = arr[r];
        arr[r] = temp;
    }

    int pivotLow = arr[p];
    int pivotHigh = arr[r];

    int low = p;
    int high = r;

    for(int j=p; j<=r; j++) {
        if(arr[j]>pivotHigh) {
            high--;
            int temp = arr[j];
            arr[j] = arr[high];
            arr[high] = temp;
        }
        if(arr[j]<pivotLow) {
            low++;
            int temp = arr[j];
            arr[j] = arr[low];
            arr[low] = temp;
        }
    }
    int temp1 = arr[p];
    arr[p] = arr[low];
    arr[low] = temp1;
    int temp2 = arr[r];
    arr[r] = arr[high];
    arr[high] = temp2;

    int pivots[] = {low, high};
    return pivots;
}
public static void quickSort2Pivots(int[] arr, int p, int r) {
    if(p<r) {
        int[] pivots = partition2Pivots(arr, p, r);
        quickSort2Pivots(arr, p, pivots[0]);
        quickSort2Pivots(arr, pivots[0]+1, pivots[1]-1);
        quickSort2Pivots(arr, pivots[1], r);
    }
}

Answer 1

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

Но сначала приведите пример неудачного случая, какминимально, насколько это возможно.

Кроме того, вы можете сохранить большой объем кода, а также возможные ошибки, если инкапсулируете код для замены двух элементов массива в функции swap (arr, i, j).