quicksort.py

def quicksort(arr, left, right):
    if left < right:
        partition_pos = partition(arr, left, right)
        quicksort(arr, left, partition_pos - 1)
        quicksort(arr, partition_pos + 1, right)

def partition(arr, left, right):
    i = left
    j = right - 1
    pivot = arr[right]

    while i < j:
        while i < right and arr[i] < pivot:
            i += 1
        while j > left and arr[j] >= pivot:
            j -= 1
        
        if i < j:
            tmp = arr[i]
            arr[i] = arr[j]
            arr[j] = tmp
    
    if arr[i] > pivot:
        tmp = arr[i]
        arr[i] = arr[right]
        arr[right] = tmp
    
    return i


a = [3, 4, 1, 2, 1, 8, 5, 6]
quicksort(a, 0, len(a) - 1)
print(a)