Как работает разделение Хоара в QuickSort?

Вот псевдокод прямо из книги (CORMEN):

Partition(A,p,r)
        x=A[p]
        i=p-1
        j=r+1 
        while(TRUE)
            repeat
                j=j-1
            until A[j]<=x
            repeat
                i=i+1
            until A[i]>=x
            if i<j
                SWAP A[i] <=> A[j]
            else return j

Вот код на С++:

#include<bits/stdc++.h>
using namespace std;


int partition(int a[], int low, int high)
{
    int pivot = a[low];
    int i = low - 1;
    int j = high + 1;
    while (1)
    {
        do {
            i++;
        } while (a[i] < pivot);

        do {
            j--;
        } while (a[j] > pivot);

        if (i >= j) {
            cout<<j<<endl;
            return j;

        }

        swap(a[i], a[j]);
    }
}


/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
        at right place*/
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int arr[] = {7,3,2,6,4,1,3,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"partition:\n";
    partition(arr,0,7);
    printArray(arr, n);

    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Если я использую этот массив на входе:

[5,3,2,6,4,1,3,7]

все работает логически хорошо, потому что массив, возвращаемый разделением, будет:

[3,3,2,1,4,6,5,7] 

Завершение i = 5 и j = 4, поэтому мой стержень равен 4. И все элементы слева от 4 являются второстепенными, а все справа - основными.

Теперь, если я использую этот массив на входе:

[7,3,2,6,4,1,3,5]

У меня будет такая ситуация в конце раздела

[5,3,2,6,4,1,3,7]

который вернется ко мне как точка опоры j = 6, то есть 3. Теперь элементы слева от 3 не все второстепенные, а справа - основные. Но как это возможно? Разве я не должен иметь элементы слева от основного минора и справа от мажора?