def partition(items, low, high):
    """Return index `p` after in-place partitioning given items in range
    `[low...high]` by choosing a pivot (the right-most element) from
    that range, moving pivot into index `p`, items less than pivot into range
    `[low...p-1]`, and items greater than pivot into range `[p+1...high]`.
    DONE: Running time: O(n), since each element is compared to the pivot.
    DONE: Memory usage: O(1), since the items are sorted in place."""
    # DONE: Choose a pivot by selecting the right-most element
    pivot = items[high]
    p = low
    # DONE: Loop through all items in range [low...high]
    for i in range(low, high):
        # DONE: Move items less than pivot into front of range [low...p-1]
        # DONE: Move items greater than pivot into back of range [p+1...high]
        if items[i] <= pivot:
            items[p], items[i] = items[i], items[p]
            p += 1
    # DONE: Move pivot item into final position [p] and return index p
    items[p], items[high] = items[high], items[p]
    return p