Быстрая сортировка выбирает опорный элемент, делит массив на элементы меньше и не меньше опорного и рекурсивно сортирует обе части. Слияние не нужно: после partition опорный уже на своём месте. Среднее время O(n log n), худший случай O(n²), память O(log n) на стек. Шаг partition тот же, что в quickselect, только теперь мы спускаемся в обе стороны.

Инварианты разбиений
Инварианты разбиений

Разбиение Ломуто и медиана трёх

Опорный — медиана первого, среднего и последнего элементов, переставленная в конец. i — граница зоны «меньше опорного». Рекурсия идёт в меньшую часть, а по большей продолжает цикл (см. раздел про глубину ниже).

python
def median_of_three(a, lo, hi):
    mid = (lo + hi) // 2
    x, y, z = a[lo], a[mid], a[hi]
    if x < y:
        if y < z:
            return mid
        return hi if x < z else lo
    if x < z:
        return lo
    return hi if y < z else mid

def partition(a, lo, hi):
    m = median_of_three(a, lo, hi)
    a[m], a[hi] = a[hi], a[m]
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

def quick_sort(a):
    a = list(a)

    def sort(lo, hi):
        while lo < hi:
            p = partition(a, lo, hi)
            if p - lo < hi - p:
                sort(lo, p - 1)
                lo = p + 1
            else:
                sort(p + 1, hi)
                hi = p - 1

    sort(0, len(a) - 1)
    return a

print(quick_sort([5, 2, 9, 1, 5, 6, 3]))
print(quick_sort([]))
print(quick_sort([4, 4, 4]))
text
[1, 2, 3, 5, 5, 6, 9]
[]
[4, 4, 4]

Разбиение Хоара