Untitled

def quick_sort(array, low, high):
    if low < high:
        lt, gt = partition(array, low, high)
        quick_sort(array, low, lt - 1)
        quick_sort(array, gt + 1, high)

def partition(array, low, high):
    pivot = array[(high + low) // 2]
    lt = low  # pointer for elements less than pivot
    gt = high  # pointer for elements greater than pivot
    i = low  # pointer for current element

    while i <= gt:
        if array[i] < pivot:
            array[lt], array[i] = array[i], array[lt]
            lt += 1
            i += 1
        elif array[i] > pivot:
            array[gt], array[i] = array[i], array[gt]
            gt -= 1
        else:
            i += 1
    
    return lt, gt