Как вы доказываете или иллюстрируете, что быстрая сортировка слиянием является нестабильным алгоритмом?

Чтобы доказать неустойчивость алгоритма, достаточно одного контрпримера: рассмотрим шаги, предпринятые для сортировки массива из 4 элементов A B C D, равных по сравнению с предикатом less.

• sort(a, 0, 3) рекурсирует на 2 подмассива:
• sort(a, 0, 1) который снова рекурсирует
• sort(a, 0, 0) который немедленно возвращается
• sort(a, 1, 1) который немедленно возвращается
• merge(a, 0, 0, 1) не меняет порядок A B
• sort(a, 2, 3) который рекурсивно
• sort(a, 2, 2) который немедленно возвращается
• sort(a, 3, 3) который немедленно возвращается
• merge(a, 2, 2, 3) не меняет порядок C D
• merge(a, 0, 1, 3) копирует элементы A B C D в t в порядке A B D C, тогда все сравнения в цикле слияния оцениваются как ложные, поэтому элементы, скопированные обратно в a, находятся в том же порядке, скопированы из t[i++]: A B D C, что доказывает нестабильность алгоритма сортировки, то есть: относительный порядок элементов, которые сравниваются равными, не сохраняется.

Алгоритм сортировки, сохраняющий «равные» элементы в одном и том же порядке, считается стабильным. Таким образом, нестабильный означает: у вас есть несколько одинаковых элементов, и когда вы сортируете общий список/массив, на выходе этой сортировки эти равные элементы (потенциально) отображаются в другой порядок.

Предположим, например, что у вас есть класс Person, и реализовано равенство, чтобы смотреть только на фамилию и игнорировать имя.

Теперь предположим, что у вас есть два объекта Person, представляющие «John Doe» и «Jane Doe». Они находятся в вашем несортированном списке именно в таком порядке.

Стабильный означает: вы всегда заканчиваете тем, что «Джон Доу» появляется перед «Джейн Доу». С нестабильной сортировкой у вас нет такой гарантии.

Другими словами: вам нужно создать класс, который имеет как минимум два атрибута. Затем вам нужно определить compareTo(), чтобы полагаться только на одно из двух свойств.

Затем вы создаете примерный список объектов этого класса, а затем достаточно долго экспериментируете, пока не найдете пример, в котором отсортированный список показывает, что одинаковые объекты изменили порядок.

Другими словами: создайте список (p1, p2, p3, p4, ...), отсортируйте его, а затем посмотрите на результат, который, возможно, говорит ... p4, p3 ... хотя p4 и p3 считаются " равный".

И наконец: на самом деле это был бы очень хороший вариант использования некоторой среды тестирования на основе свойств, такой как Быстрая проверка. Используя такую ​​структуру, вам потребуется:

• создайте «генератор», который может создавать «случайные» объекты некоторого класса, по которому вы позже сортируете (где вы искажаете генератор, чтобы гарантировать, что вы получите из него кучу «равных» объектов)
• затем попросите фреймворк проверить базовое «утверждение», что порядок «равных» объектов до и после сортировки не должен меняться.

И пусть фреймворк сделает свое волшебство...

Чтобы доказать неустойчивость алгоритма сортировки, нужно найти только один сбой. Доказательство стабильности алгоритма сортировки было бы более сложным. Один из способов проверить наличие ошибки — использовать массив целых чисел и разделить целые числа на две части: старшие 8 бит — псевдослучайное значение, младшие 24 бита — индекс целого числа (от 0 до count-1). Затем запустите сортировку, используя для сравнения только старшие 8 бит, например, в C:

    if((b[j]&0xff000000) < (b[i]&0xff000000)) ...

После завершения сортировки проверьте правильность массива, используя все 32 бита.

Используя этот метод, я смог подтвердить, что этот вариант сортировки слиянием нестабилен.

По-видимому, причина, по которой это называется «быстрой» сортировкой слиянием, заключается в том, что при выполнении слияния не проверяется конец прогона. Левая часть копируется в aux[] в прямом порядке от lo до mid, а правая копируется в aux[] в обратном порядке от hi до mid+1. Затем слияние начинается с обоих концов (lo и hi) и работает по направлению к середине (mid и mid+1), левый работает с помощью i вперед от lo к середине, правый выполняется назад с помощью j от привет до середины+1. Так как нет проверки достижения конца выполнения, i может быть увеличено выше середины (потенциальная проблема со стабильностью) или j может быть уменьшено ниже середины+1 (не вопрос стабильности). Стабильность нарушается в случае, когда i увеличивается выше середины, а aux[mid+1] == aux[mid+2], два самых высоких элемента из исходного правого ряда. В этом случае элементы копируются в обратном порядке.

Хотя в книге это называется быстрой сортировкой слиянием, было бы быстрее не копировать данные в aux, а вместо этого изменять направление слияния в зависимости от уровня рекурсии. Для сверху вниз это можно сделать с помощью копии одного типа и замены ссылок на массивы в рекурсивных вызовах, таких как этот пример из вики:

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

Исходной копии можно избежать, используя пару взаимно рекурсивных функций, одна из которых приводит к результату в a[], а другая — к результату в b[].

Немного быстрее сортировка слиянием снизу вверх, поскольку она пропускает все рекурсивное разбиение и сохранение индексов в стеке. В этом случае направление слияния основано на проходе слияния. Чтобы количество проходов оставалось четным, можно заранее проверить количество нечетных проходов и поменять местами пары элементов перед началом первого прохода сортировки слиянием снизу вверх.