A faster sorting algorithm given a magic data structure?

Suppose that you have a magic data structure that represents a linear sequence of elements that supports lookup, insertion, and deletion of any i开发者_开发百科ndex in worst-case O(1) time. (I'm pretty sure that no such structure is possible given the memory model of modern machines, but let's just suppose that we have one for the fun of it).

A friend of mine pointed out that if you have this data structure, then you can build a cool sorting algorithm for integers that runs in expected O(n lg lg n) time as follows. First, create one of the magic data structures mentioned above. Next, for each element in the input array, use interpolation search to find, in expected O(lg lg n) time, the index in that magic array in which the element belongs, then in O(1) time insert the element. Finally, in O(n) time, read off the sorted magic data structure. This makes n calls to the O(lg lg n) interpolation search, which will run in O(n lg lg n) time.

I understand that this above approach is not going to give worst-case O(n lg lg n) time for sorting, since there are pathologically bad input arrays that if used in interpolation search would degenerate the search to O(n²) time. My question is, given this magic data structure, what is the fastest integer sorting algorithm that can be built, assuming we care only about the worst-case runtime of the algorithm?

(This may be a better fit on cstheory, but I'd figured I'd ask here first since I've gotten some great algorithms answers in the past.)

Counting sort is of O(n) complexity http://en.wikipedia.org/wiki/Counting_sort . However, it is not always convenient to use, because temporary array that is created by the algorithm has size of maximum integer value of sorted array.

Any comparison based sort requires O(n log(n)) comparisons in the average case, let alone the worst one. See http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list for details of why. Therefore no comparison based sort can beat that lower limit even with your magic data structure.

Non-comparison based sorts (eg radix) tend to be designed in a way where they would not benefit from your data structure, so I don't think it would make a difference to them.

Interpolation search requires an operation beyond just comparison, and thus can not be used in a comparison sort. If you can run an interpolation, you can probably do radix like operations, and thus perform better than O(n log n), and magic data structures will help.

Counting sort sorts in O(n) on your magic structure, which is about as fast as any integer sorting algorithm is likely to be. An interesting, and potentially unsolved question is how fast is the fastest parallel sorting algorithm for integers. Given an infinite number of processors (like in a non deterministic turing machine), I expect you can do better than O(n), but I dont know how much.