from typing import List


def _partition(nums: List[int], left: int, right: int) -> int:
    """
    Helper function to partition the given sub-list.
    :param nums: list[int]
    :param left: int
    :param right: int
    :return: int
    """
    # The pivot has already been moved to the left.
    pivot = nums[left]

    # Iterate over the sub-list, use a pointer to keep track of the smaller
    # part, and swap the current number with the pointer as necessary
    smaller_ptr = left + 1
    i = left + 1
    while True:
        while i <= right and nums[i] > pivot:
            i += 1
        if i > right:
            break
        if i != smaller_ptr:
            nums[smaller_ptr], nums[i] = nums[i], nums[smaller_ptr]
        smaller_ptr += 1
        i += 1
    if left != smaller_ptr - 1:
        nums[left], nums[smaller_ptr - 1] = nums[smaller_ptr - 1], nums[left]
    return smaller_ptr - 1