Hoare partition not working when more than one value is equal to pivot

Question

I'm trying to write my own hoare partition function to better understand it. I thought I followed its definition and pseudo-code well but even though it seems to work as expected on many occasions, it falls apart and goes into infinite loop when a list with multiple values equal to pivot are passed in. Where is my mistake, how should I modify this to fix the bug?

def partition(lst, left_index, right_index):
    pivot = lst[right_index]


    while True:
        #Increment left index until value at that index is greater or equal to pivot
        while True:
            if lst[left_index] >= pivot: break
            left_index += 1

        #Increment right index until value at that index is less or equal to pivot
        while True:
            if lst[right_index] <= pivot: break
            right_index -= 1

        if left_index < right_index:
            lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
        else:
            return right_index

return partition(0, end)

Answer 1

You are testing for equality with pivot value in both lst[left_index] >= pivot and lst[right_index] <= pivot. This effectively prevents both indices from skipping over pivot-valued elements. Therefore, when two or more pivot-valued elements are pushed toward the middle of your list, left_index and right_index get separated by an unsurmountable barrier. Delete the equal sign in one of those breaking lines, and the non-halting problem will be gone.

However, as a result of this change the loop that moves left_index may push it by one position above right_index and even go out of bounds when right_index stays at its initial position. Similarly, the loop that moves right_index may push it by one position below left_index and even go out of bounds when left_index stays at its initial position. To prevent that from happening you must change while True: in those loops to while left_index < right_index:.

Note that the partitioning will be slightly different depending on whether you remove the equality check for left_index or right_index. It matters for the boundary cases, when the pivot element turns out to be the smallest or the largest value in the list. Taking into account that in the beginning right_index represents an internal position with respect to the input range and left_index points to a boundary position, you must allow left_index to skip over pivot values whereas right_index must be instructed to stop at pivot values (the opposite logic would enable left_index staying at its initial position till the end of the algorithm, while right_index could be pushed all the way down to left_index, producing no partitioning whatsoever).

Thus the corrected code will be this:

def partition(lst, left_index, right_index):
    pivot = lst[right_index]

    while True:
        while left_index < right_index and lst[left_index] <= pivot:
            left_index += 1

        while left_index < right_index and lst[right_index] > pivot:
            right_index -= 1

        if left_index < right_index:
            lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
        else:
            return right_index