Как работает быстрая сортировка?

• Выбираем опорный элемент.
• Числа меньше опорного, влево, больше, вправо.
• Опорный встаёт на финальное место.
• Повторяем для каждой половины рекурсивно.

Быстрая сортировка сортирует массив на месте, без создания копий, и в среднем укладывается в n log n сравнений. Причина в том, как устроено разбиение. Берёшь опорный элемент, не важно какой, хоть последний, хоть случайный, и заводишь два указателя с разных концов массива. Один идёт слева направо, ищет число больше опорного. Другой идёт справа налево, ищет число меньше опорного. Как только оба нашли что искали, меняешь числа местами и продолжаешь двигать указатели, пока они не встретятся. Это называют разбиением, partition, и после него опорный элемент оказывается ровно на своём финальном месте: слева от него всё меньше, справа всё больше. Дальше рекурсия применяется отдельно к левому куску и отдельно к правому, каждый раз с новым опорным элементом. Массив не копируется, всё происходит внутри тех же ячеек памяти, поэтому сортировка экономна по памяти в отличие от сортировки слиянием. Возьми для наглядности пять чисел: 4, 1, 7, 3, 9. Опорным берём последнее, 9. Всё остальное меньше девятки, значит после первого разбиения девятка просто встаёт в конец, а слева остаётся 4, 1, 7, 3 для следующего шага. Дальше та же операция применяется рекурсивно к этому куску. Причина, по которой это быстро на практике, а не только в теории: операций сравнения и обмена мало, кэш процессора любит последовательный доступ к памяти, а рекурсия быстро сокращает размер задачи вдвое на каждом уровне. Именно поэтому эту сортировку почти всегда используют в стандартных библиотеках языков, иногда пряча за ней подстраховку на случай неудачного выбора опоры.

Идея Берём любой элемент массива, его называют опорным, и разделяем оставшиеся числа на две группы: те, что меньше опорного, и те, что больше. Опорный элемент встаёт между ними на своё окончательное место. Пример Возьмём числа 8, 3, 5, 1, 9, 2 и выберем опорным последнее число, 2. Меньше двух только 1, значит 1 уходит влево, а 8, 3, 5, 9 остаются справа. Получаем 1, 2, 8, 3, 5, 9, двойка уже стоит правильно. Повторение Дальше та же операция применяется отдельно к левой части и отдельно к правой, пока в каждой не останется один элемент или пусто. В сумме массив собирается отсортированным без единого отдельного прохода на слияние.