def partition(thelist: list, start_index: int, end_index: int) -> int:
    """
    Partitions a list into 2 and returns the pivot index
    :param thelist The list to divide into 2 partitions to get the pivot index.
    This uses the last element as the pivot of the list
    :type thelist list
    :param start_index
    :type start_index int
    :param end_index
    :type end_index int
    :returns pivot index
    :rtype int
    """

    pivot = thelist[end_index]

    left_index = start_index
    right_index = end_index - 1

    while left_index <= right_index:

        # walk until we find something on the left side that belongs on the right (less than the pivot)
        while left_index <= end_index and thelist[left_index] < pivot:
            left_index += 1

        # walk until we find something on the right side that belongs on the left(greater than or equal to the pivot)
        while right_index >= start_index and thelist[right_index] >= pivot:
            right_index -= 1

        # swap the items at the left_index and right_index, moving the element that's smaller than the pivot to the left
        # half and the element that's larger than the pivot to the right half

        if left_index < right_index:
            thelist[right_index], thelist[left_index] = thelist[left_index], thelist[right_index]

        # unless we have looked at all the elements in the list and are done partitioning. In that case, move the pivot element
        # into it's final position
        else:
            thelist[end_index], thelist[left_index] = thelist[left_index], thelist[end_index]

    return left_index