быстрая сортировка

EN: quicksort

Алгоритм сортировки «разделяй и властвуй», выбирающий опорный элемент (pivot), разбивающий массив на элементы меньше и больше опорного, а затем рекурсивно сортирующий каждую часть. Среднее время работы — O(n log n); худший случай — O(n²), когда pivot всегда является минимумом или максимумом, что случайный выбор pivot делает маловероятным на практике.