Быстрая сортировка (сортировка Хоара).

Алгоритм

Худшее O(n^2), среднее O(n log n)

Выбор опорного элемента по принципу "встреча троих"

1. Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива.
2. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на два непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные, большие» (если хотим без использования допмассивом, то ставим указатели в начало и конец, идём по началу, пока элемент меньше пропускаем, встречаем больше или равно => запускаем указатель с конца, аналогично сравниваем, но с условием больше опорного, встречаем элемент меньше => меняем элементы под указателями друг с другом, продолжаем)
3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

import random  
  
def quickSort(arr):  
    if len(arr) <= 1:  
        return arr  
	
    q = random.choice(arr)  
    left = []  
    middle = []  
    right = []  
	
    for n in arr:  
        if n < q:  
            left.append(n)  
        elif n > q:  
            right.append(n)  
        else:  
            middle.append(n)  
	
    return quickSort(left) + middle + quickSort(right)