from typing import List
from typing import Any


def _partition(items: List[Any], left: int, right: int) -> int:
    """Partitions the array around the pivot value.

    Picks a pivot value and sorts everything to the left <= pivot,
    and everything greater than pivot to the right.

    At the end, the pivot will be in its correct position.

    Example: [100, 5, -2, 1, 52, 3, 4]

    1. Pick a pivot value. (rightmost item)
    2. Set a pointer (i) to the left -- this is the greatest element.
    3. Iterate until the pivot.
        3.1 If we find an element <= pivot
        3.2 Swap it with the greater value (i)
        3.3 Increment greater element pivot (i)
    4. Swap the pivot with the greater element pointer
    5. Return the pivot position.

    Args:
        items: The list of items to sort.
        left: The leftmost index.
        right: The rightmost index.

    Returns: The index of the pivot value.
    """
    # Choose rightmost element as pivot.
    pivot_val = items[right]

    # Greater element pointer
    # We know the pointer must point to something greater
    # because if not it would have been swapped.
    i = left

    for j in range(left, right):
        if items[j] <= pivot_val:
            # An item smaller than the pivot was found:
            # Swap it with the greater element (i)
            items[i], items[j] = items[j], items[i]
            i += 1

    # Swap the pivot element with the greater element
    items[i], items[right] = items[right], items[i]

    # Return position where partition finished
    return i