# Title: Quick sort
# Heading: Python Program for Quick Sort
# Level: intermediate
# Tags: sorting, quick sort, quicksort, partition, divide and conquer
# Time: O(n log n)
# Space: O(log n)
# About: Sorts a list in place by moving smaller items before a pivot and the rest after it, then sorting each side: O(n log n) time on average.

def quick_sort(items, low=0, high=None):
    """Sort items[low:high + 1] in place, smallest first."""
    if high is None:
        high = len(items) - 1
    if low < high:
        p = partition(items, low, high)
        quick_sort(items, low, p - 1)   # the items before the pivot
        quick_sort(items, p + 1, high)  # the items after it


def partition(items, low, high):
    """Put the pivot, items[high], in its sorted place; return it."""
    pivot = items[high]
    i = low  # where the next item smaller than the pivot goes
    for j in range(low, high):
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]
    return i


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
quick_sort(numbers)
print("After: ", numbers)