Как работает метод Франческини?

В Wikipedia упоминается, что этот метод сортирует массив в O (n log n), но он также стабилен и на месте. Это звучит как очень хороший алгоритм сортировки, поскольку ни один другой алгоритм сортировки не делает все это сразу (Вставка Сортировка не O (n log n), "Куча сортировки" нестабильна, Quicksort (или Introsort) не находится на месте или стабильно, Mergesort не на месте). Однако в википедии упоминается только название, и ничего больше. В качестве ссылки он идет на Франческини, Джанни (1 июня 2007 г.). "Сортировка" Стабильно "," Место ", с помощью O (n log n)" Сравнение "и" O (n) "). Теория вычислительных систем 40 (4): 327-353. Однако на самом деле это не объясняет, как это работает на самом деле, оно показывает больше причин, по которым оно существует.

Мой вопрос заключается в том, как работает этот метод (какие шаги он делает на самом деле) и почему так мало ресурсов связано с ним, учитывая, что нет других известных методов O (n log n), устойчивых на месте сортировки.

Ответ 1

поскольку нет других известных O (n log n) устойчивых методов локального сортирования.

Это достаточно легко, чтобы реализовать слияние с использованием O (log n) дополнительного пространства, которое, на мой взгляд, достаточно близко на практике.

Фактически существует вариант сортировки слияния, который является стабильным и использует только O (1) дополнительную память: "Практическое объединение на месте" Katajainen, Pasanen и Teuhola. Он имеет оптимальное время выполнения O (n log n), но он не является оптимальным, поскольку он использует операции перемещения элемента Ω (n log n), когда это можно сделать с помощью O (n), как показано в документе Франческини.

Кажется, он работает медленнее, чем традиционный тип слияния, но не с большим отрывом. Напротив, версия Franceschini выглядит намного сложнее и имеет огромные постоянные накладные расходы.

Ответ 2

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

Использование такого метода превратило бы HeapSort, например, в устойчивый алгоритм O (n * logn) на месте,

Однако, поскольку нам нужно хранить O (1) "дополнительных" данных для каждой записи, нам технически нужно O (n) дополнительного пространства, поэтому это не реально на месте, если вы не рассматриваете исходный индекс часть ключа. Франческини не потребует каких-либо дополнительных данных.

Ответ 3

Бумагу можно найти здесь: http://www.springerlink.com/content/d7348168624070v7/. Однако он довольно сложный, раскалываясь на случаи о том, является ли число различных элементов o (n/(log n) ^ 3) или нет. Вероятно, скрытые константы делают это непривлекательным решением для сортировки на практике, тем более, что сортировка обычно не должна быть стабильной, если вторичная информация не сохраняется в отсортированных элементах, которые необходимо сохранить в исходном порядке.