给出一个神奇的数据结构,更快的排序算法？

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 ²)时间.我的问题是,鉴于这种神奇的数据结构,假设我们只关心算法的最坏情况运行时,那么可以构建的最快整数排序算法是什么？

(这可能更适合于cstheory,但我想我先问这里,因为我在过去得到了一些很棒的算法答案.)

Answer 1

计数排序的复杂度为 O(n) http://en.wikipedia.org/wiki/Counting_sort。然而，使用起来并不总是方便，因为算法创建的临时数组的大小是排序数组的最大整数值。