假设您有一个魔术数据结构，表示在最坏情况下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（n2）时间 . 我的问题是，假设我们只关心算法的最坏情况运行时，给定这个神奇的数据结构 what is the fastest integer sorting algorithm that can be built ？
（这可能更适合于cstheory，但我想我先问这里，因为我在过去得到了一些很棒的算法答案 . ）
3 回答
计数排序是O（n）复杂度http://en.wikipedia.org/wiki/Counting_sort . 但是，使用并不总是方便，因为算法创建的临时数组的大小是已排序数组的最大整数值 .
任何基于比较的排序都需要在平均情况下进行
O(n log(n))比较，更不用说最差的比较了 . 有关原因的详细信息，请参见http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list . 因此，即使使用魔法数据结构，也没有基于比较的排序可以超过该下限 .基于非比较的排序（例如基数）倾向于以不会从数据结构中受益的方式设计，因此我认为它不会对它们产生影响 .
插值搜索需要不仅仅是比较的操作，因此不能用于比较排序 . 如果你可以运行插值，你可以做基数操作，因此比O（n log n）表现更好，魔术数据结构也会有所帮助 .
在你的魔法结构上对O（n）中的排序进行排序，这与任何整数排序算法的速度一样快 . 一个有趣且可能未解决的问题是整数的最快并行排序算法的速度有多快 . 鉴于无限数量的处理器（如非确定性图灵机），我希望你能比O（n）做得更好，但我不知道多少 .