def partition(arr, low, high):
    """Take the last element as the pivot,
     and place that element in the correct sorted position by moving all smaller items to the left of the pivot
     and all larger items to the right of the pivot"""
    # Set i to be index of smaller element
    i = low - 1

    # Assume last element as pivot
    pivot = arr[high]

    # Iterate over indices from low to high
    for j in range(low, high):

        # If you encounter an element smaller than the pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            i += 1
            # swap the smaller and larger elements
            arr[i], arr[j] = arr[j], arr[i]
    # once you reach the end, swap the pivot with the index larger element
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    # return index of pivot
    return i + 1