Quick sort with equivalent elements. Θ(nlgn)

def partition(array, p, r):
    x = array[r]
    j = i = p - 1
    for k in range(p, r):
        if array[k] < x:
            i += 1
            j += 1
            # Crucial: Assignment order must be rotative.
            array[k], array[j], array[i] = array[j], array[i], array[k]
        elif array[k] == x:
            j += 1
            array[j], array[k] = array[k], array[j]
    i += 1
    j += 1
    array[j], array[r] = array[r], array[j]
    return i, j

def quickSort(array, p, r):
    if p < r:
        i, j = partition(array, p, r)
        print('i j =', i, j)
        quickSort(array, p, i-1)
        quickSort(array, j+1, r)