Я с трудом разбираюсь в быстрой сортировке, большинство демонстраций и объяснений не учитывают того, что на самом деле происходит (http://me.dt.in.th/page/Quicksort/ например).

Википедия говорит:

Выберите элемент, называемый сводной, из массива. Разбиение: переупорядочить массив таким образом, чтобы все элементы со значениями, меньшими, чем сводка, предшествовали сводке, а все элементы со значениями, превышающими сводку, следовали за ней (равные значения могут идти в любом случае). После этого разделения шарнир находится в своем окончательном положении. Это называется операцией с разделами. Рекурсивно примените вышеуказанные шаги к подмножеству элементов с меньшими значениями и отдельно к подмножеству элементов с большими значениями.

Как это будет работать с массивом 9,1,7,8,8, например, с 7 в качестве оси? 9 нужно переместить вправо от оси, все реализации быстрой сортировки находятся на месте операций, кажется, поэтому мы не можем добавить его после 8,8, поэтому единственный вариант - поменять 9 на 7.

Сейчас массив 7,1,9,8,8. Идея быстрой сортировки заключается в том, что теперь мы должны рекурсивно сортировать части слева и справа от оси. Поворот теперь находится в позиции 0 массива, то есть левой части нет, поэтому мы можем отсортировать только правую часть. Это бесполезно, так как 7> 1, так что стержень оказался в неправильном месте.

На этом изображении 4 - это точка поворота, тогда почему 5 движется почти полностью влево? Это больше, чем 4! После большого количества обмена это заканчивает тем, что было отсортировано, но я не понимаю, как это случилось.