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

Предположим, у вас есть волшебная структура данных, которая представляет линейную последовательность элементов, которая поддерживает поиск, вставку и удаление любого индекса в худшем случае за время 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 ² ) раз. У меня вопрос, учитывая эту волшебную структуру данных, какой алгоритм сортировки целых чисел самый быстрый, который может быть построен , предполагая, что мы заботимся только о наихудшем времени выполнения алгоритма?

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