Quicksort — это алгоритм сортировки типа "разделяй и властвуй", который выбирает опорный элемент, разбивает элементы на меньшие и большие, а затем рекурсивно сортирует обе части. В среднем O(n log n), в худшем случае O(n²).
Идея
Разбиение размещает опорный элемент на его окончательной позиции в отсортированном массиве; всё слева меньше, всё справа больше. Рекурсивно повторяй на обеих сторонах.
