Алгоритм быстрой сортировки: n log n или n² при неудачном выборе опорного элемента

Быстрая сортировка объяснена с нуля: как работает разбиение, почему быстрая сортировка имеет сложность O(n log n), когда опорное число находится близко к середине, и почему неудачное опорное число делает её сложность O(n²). Никакого кода на каком-либо языке, только один восьмизначный массив (5, 3, 8, 1, 7, 2, 4, 6), обработанный на доске, каждое движение пальца и каждая галочка. Он открывается на основе двух подсчетов, измеренных на миллионе чисел. В случайном порядке быстрая сортировка выполняет около 26 миллионов проверок. Уже отсортированная, с первым числом в качестве опорного, она выполняет полтриллиона (500 001 499 998, если считать в реальном случае). Те же числа, те же правила: единственное различие — в том, где находится опорное число. Разделение — это двухпальцевая версия из учебников DAA: первое число — это опорное, левый палец ищет число, которое не должно быть слева, правый — число, которое не должно быть справа, они меняются местами, и когда пальцы пересекаются (или встречаются), опорное число перемещается на свое последнее место и больше не сдвигается. Затем быстрая сортировка делает то же самое с каждой стороны, и когда каждый элемент представляет собой одно число, массив отсортирован. Ничего никогда не объединяется, и нет второго массива, только краткая заметка для каждого элемента, работа над которым еще не завершена. Подсчет: каждое число проверяется примерно один раз для каждой строки, в которой оно находится. Когда опорные числа оказываются ближе к середине, элементы примерно делят каждую строку пополам, поэтому получается примерно log n строк: n log n, лучший случай. Случайный порядок — это средний случай: около 25 строк на число и 26 миллионов проверок при миллионе. Когда опорный элемент отсекает всего одно число, как это происходит с первым числом в отсортированном наборе данных, типичное число обрабатывает полмиллиона строк: n²/2 — наихудший случай. Из всех 40 320 порядков из восьми чисел ни один не требует больше проверок, чем 42 проверки в отсортированном порядке. Решение — случайный опорный элемент. Почему бы не использовать средний элемент? Любое правило, выбирающее одни и те же позиции, может быть обыграно тем, кто предоставляет числа: построенный список из 20 000 чисел требует от версии со средним элементом почти 20 000 строк, и медиана из трех чисел также проходит через эти строки. Почему бы не использовать точное среднее значение (медиана медиан)? У него нет плохого случая, но для его нахождения потребовалось 148 миллионов дополнительных проверок на миллион чисел, 167 миллионов в общей сложности против 26 миллионов при случайном выборе. Случайный выбор в половине случаев приводит к тому, что фигура попадает в среднюю половину своего фрагмента, а уменьшение фрагментов до трех четвертей по-прежнему является фиксированным кратным делениям пополам, поэтому сложность остается O(n log n). Наконец, равные числа: оба пальца останавливаются на числе, равном опорному, что позволяет сохранить сто тысяч равных чисел примерно на уровне 1,5 миллиона проверок вместо пяти миллиардов. Далее: сортировка слиянием, которая получает n log n в обратном порядке, сравнивая после разреза, а не до него.