def partition(arr, left, right, pivot_index):
    """
    Partition the array into three groups: less that pivot, equal to it and more than pivot

    Args:
       input_list(list): Input List
       left(int): start index
       right(int): end index
       pivot_index(int): index of the pivot element

    Returns:
       (int),(int): left and right index - boundary of the pivot element on the right place
       when array is sorted. All elements to the left index are smaller than the pivot,
       all element to the right inidex are bigger. All elements between left and right (including them)
       are equla to the pivot.
    """
    pivot = arr[pivot_index]
    store_index = left

    # move pivot to the end
    arr[right], arr[pivot_index] = arr[pivot_index], arr[right]

    # move all elements smaller than or equal to pivot to the left
    for i in range(left, right):
        if arr[i] <= pivot:
            arr[store_index], arr[i] = arr[i], arr[store_index]
            store_index += 1

    # move the pivot to its final position
    arr[right], arr[store_index] = arr[store_index], arr[right]

    # find left boundary in case of pivot duplicates
    pivot_left_index = store_index
    while pivot_left_index >= 0 and arr[pivot_left_index] == pivot:
        pivot_left_index -= 1

    return (pivot_left_index + 1, store_index)