"""
Быстрая сортировка
Этот алгоритм также относится к алгоритмам 
«разделяй и властвуй». Его используют чаще 
других алгоритмов, описанных в этой статье. 
При правильной конфигурации он чрезвычайно эффективен и 
не требует дополнительной памяти, в отличие от сортировки 
слиянием. Массив разделяется на две части по разные 
стороны от опорного элемента. В процессе сортировки элементы 
меньше опорного помещаются перед ним, а равные или 
большие —позади.

Алгоритм
Быстрая сортировка начинается с разбиения списка и 
выбора одного из элементов в качестве опорного. 
А всё остальное передвигаем так, 
чтобы этот элемент встал на своё место. 
Все элементы меньше него перемещаются влево, а 
равные и большие элементы перемещаются вправо.

Реализация
Существует много вариаций данного метода. 
Способ разбиения массива, рассмотренный здесь, 
соответствует схеме Хоара (создателя данного алгоритма).

Время выполнения
В среднем время выполнения быстрой 
сортировки составляет O(n log n).

Обратите внимание, что алгоритм быстрой 
сортировки будет работать медленно, если опорный 
элемент равен наименьшему или наибольшему элементам списка. 
При таких условиях, в отличие от сортировок кучей и 
слиянием, обе из которых имеют в худшем случае 
время сортировки O(n log n), быстрая сортировка в 
худшем случае будет выполняться O(n²).
"""

def partition(nums, low, high):  
    # Выбираем средний элемент в качестве опорного
    # Также возможен выбор первого, последнего
    # или произвольного элементов в качестве опорного
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1

        j -= 1
        while nums[j] > pivot:
            j -= 1

        if i >= j:
            return j

        # Если элемент с индексом i (слева от опорного) больше, чем
        # элемент с индексом j (справа от опорного), меняем их местами
        nums[i], nums[j] = nums[j], nums[i]

def quick_sort(nums):  
    # Создадим вспомогательную функцию, которая вызывается рекурсивно
    def _quick_sort(items, low, high):
        if low < high:
            # This is the index after the pivot, where our lists are split
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)

    _quick_sort(nums, 0, len(nums) - 1)

# Проверяем, что оно работает
random_list_of_nums = [22, 5, 1, 18, 99]  
quick_sort(random_list_of_nums)  
print(random_list_of_nums) 