def partition(arr, left, right):
    """
      *--------*----------*-----------*
    left      mid      frontier      right

    left is the pivot, it has been moved to the beginning of the array.
    frontier marks all the elements we've alreay looked at.
    mid is the new index of the pivot, everything to the left is smaller than
        pivot, everything to the right is larger.
    """
    mid = left + 1
    frontier = left + 1
    while frontier < right:
        if arr[frontier] < arr[left]:
            arr[frontier], arr[mid] = arr[mid], arr[frontier]
            mid += 1
        frontier += 1
    arr[left], arr[mid] = arr[mid], arr[left]
    return mid