Hoare partitioning algorithm for duplicate pivot value

Question

Following is a Hoare partitioning algorithm per Wikipedia.

Pseudo-code from Wikipedia:

algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i ≥ j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

A java implementation:

public class Main
{
    public static void main(String[] args) {
        int[] arr = new int[] { 2, 1, 2, 4, 3 };
        Hoare.partition(arr, 0, 4);

        for (int x : arr) System.out.println(x);
    }
}

class Hoare
{
    private static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 

    public static int partition(int []arr, int low, int high)
    {
        int pivot = arr[(low + high) / 2]; // pivot is 2 for this case.
        // Expected out is:
        // 1 2 2 3 4
        // or
        // 1 2 2 4 3
        //
        // Actual output is:
        // 2 1 2 4 3
        // Since 3 and 4 are greater than 2, then the partitioning isn't working.

        int i = low - 1;
        int j = high + 1;
     
        while(true)
        {
            do {
                i++;
            }
            while (arr[i] < pivot);
            
            do {
                j--;
            }
            while (arr[j] > pivot);
            
            if (i >= j)
            {
                return j;
            }
            
            Swap(arr, i, j);
        }
    }
}

Why is the output wrong (indicated in code comments)? Is that a known limitation of Hoare algorithm? Is my implementation or Wikipedia's pseudocode is incorrect?

Answer 1

The Hoare algorithm guarantees that all elements before the pivot are less than or equal to the pivot value and all elements after the pivot are greater than or equal to the pivot value.

That also means that the pivot value is at the correct index in the final sorted array. That is important for the quicksort algorithm.

The Hoare partition does not guarantee that all elements equal to the pivot value are consecutive. That is not a requirement of the quicksort algorithm, so there is no point spending any additional computational power guaranteeing it.

In other words, the implementation is correct; the result is expected; and it will work in a quicksort without problems.