Более быстрый алгоритм сортировки, учитывая волшебную структуру данных?

Question

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

Мой друг отметил, что если выЕсли у вас есть такая структура данных, то вы можете построить классный алгоритм сортировки целых чисел, который выполняется за ожидаемое время O (n lg lg n), следующим образом.Сначала создайте одну из волшебных структур данных, упомянутых выше.Затем для каждого элемента входного массива используйте интерполяционный поиск, чтобы найти в ожидаемое время O (lg lg n) индекс в том магическом массиве, к которому принадлежит элемент, а затем в O (1) время вставить элемент.Наконец, за O (n) время считайте отсортированную магическую структуру данных.Это делает n обращений к O (lg lg n) интерполяционному поиску, который будет выполняться за O (n lg lg n) раз.

Я понимаю, что вышеописанный подход не даст O в худшем случае (n lg lg n) время для сортировки, поскольку существуют патологически неверные входные массивы, которые, если их использовать при интерполяционном поиске, выродили бы поиск до времени O (n ² ).Мой вопрос, учитывая эту волшебную структуру данных, Какой самый быстрый алгоритм целочисленной сортировки может быть построен , предполагая, что мы заботимся только о времени выполнения алгоритма в худшем случае?

(Этоможет лучше подходить к теории, но я подумал, что сначала спрошу здесь, так как в прошлом я получил ответы на некоторые великолепные алгоритмы.)

Answer 1

Любая сортировка на основе сравнения требует O(n log(n)) сравнения в среднем случае, не говоря уже о худшем. Смотрите http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list, чтобы узнать, почему. Поэтому никакая сортировка, основанная на сравнении, не может преодолеть этот нижний предел даже при вашей волшебной структуре данных.

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

Answer 2

Счетная сортировка имеет сложность O (n) http://en.wikipedia.org/wiki/Counting_sort.Однако использовать его не всегда удобно, поскольку временный массив, создаваемый алгоритмом, имеет размер максимального целочисленного значения отсортированного массива.

Answer 3

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

Подсчет сортировок сортировки по O (n) на вашей магической структуре, что примерно так же быстро, как и любой алгоритм целочисленной сортировки.Интересный и потенциально нерешенный вопрос заключается в том, насколько быстрым является самый быстрый алгоритм параллельной сортировки целых чисел.Учитывая бесконечное число процессоров (как в недетерминированной машине Тьюринга), я ожидаю, что вы можете добиться большего успеха, чем O (n), но я не знаю, сколько.