def partition(arr, start, end, pivot_index):
    """
    Partitions the array such that all elements before pivot_index
    are <= pivot element, and all the elements after are >= pivot element.
    The pivot element will come at its rightful position at the end.
    Returns the rightful index of the pivot.
    """
    arr[start], arr[pivot_index] = arr[pivot_index], arr[start]
    pivot_index = start
    i = start + 1
    while i <= end:
        if arr[i] < arr[start]:
            pivot_index += 1
            arr[pivot_index], arr[i] = arr[i], arr[pivot_index]
        i += 1
    # CAREFUL: Dont forget this step!!
    arr[pivot_index], arr[start] = arr[start], arr[pivot_index]
    return pivot_index