def __partition3way__(arr, lo, hi):
    """
    Function to achieve 3-way partitioning for quicksort
    1. Start with 3 pointers (lt, i, gt), choose first element (lo) as pivot
    2. Invariant: everything to the
        (a) left of lt is less than pivot
        (b) between lt and i is equal to pivot
        (c) right of gt is larger than pivot
    3. In each iteration, while i<gt do from left to right :
        (a) if arr[i] < arr[lo] exchange arr[lt] and arr[i], increment lt and i
        (b) if arr[i] == arr[lo] increment only i
        (b) if arr[i] > arr[lo] exchange arr[gt] and arr[i], decrement gt 
    4. Return lt, gt
    """

    if hi <= lo:
        return lo, hi

    # Define lt and gt pointers
    lt = lo
    i = lt + 1
    gt = hi
    v = arr[lo]

    while i <= gt:
        if arr[i] < v:
            arr[i], arr[lt] = arr[lt], arr[i]
            i += 1
            lt += 1
        elif arr[i] > v:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1

    return lt, gt