Quick sort picks a pivot, splits the array into the elements smaller and not smaller than the pivot, and sorts both parts recursively. No merge is needed: after partition the pivot is in its final place. The average time is O(n log n), the worst case is O(n²), memory is O(log n) for the stack. The partition step is the same as in quickselect, only now we descend into both sides.

Partition invariants
Partition invariants

Lomuto partition with a median-of-three pivot

The pivot is the median of the first, middle and last elements, moved to the end. i is the border of the zone “smaller than the pivot”. The recursion goes into the smaller part and a loop continues over the larger one (see the depth section below).

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]))