Question regarding Hoare's partitioning scheme and a slight modification to it This is the pseudocode on wikipedia for Hoare's partitioning scheme:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] &lt; pivot   //Question here

        do
            j := j - 1
        while A[j] &gt; pivot 

        if i &gt;= j then
            return j

        swap A[i] with A[j]


This code finds an inversion and swaps it. Now, the problem of partitioning about a pivot is to divide an array such that all elements &lt;= pivot fall in one partition, and all elements > pivot fall in the other.

My question is simple: why not use while a[i] &lt;= pivot ?

As far as I can tell, it will work correctly, infact it would align better with the previous definition of partitioning.

If it does work, the big question is why wasn't it used in the original paper? It makes more sense and seems to be slightly faster as well (less number of swaps required).

Infact, while we're on the subject: would it be incorrect to also use while A[j] &gt;= pivot that could further reduce the number of swaps.

I know that if I'm too worried about multiple elements repeating I should use 3 way partitioning, but I'm curious about how this algorithm would work nonetheless.
Why not use while a[i] &lt;= pivot ?


You could.  It's arbitrary.  Either way will work fine.  We just have to choose one of those two choices.  They both have the same asymptotic running time.