A faster sorting algorithm gives a magic data structure?

Question

Suppose you have a magic data structure representing a linear sequence of elements that supports finding, inserting, and deleting any index in the worst case O (1). (I’m sure that such a model is not possible given the memory model of modern machines, but let's assume that we have it for fun).

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

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

(This may be better suited for cstheory, but I thought I'd ask here first, since in the past I had answers to large algorithms.)

Answer 1

Sorting sorting has O (n) complexity http://en.wikipedia.org/wiki/Counting_sort . However, this is not always convenient to use, since the temporary array created by the algorithm has the size of the maximum integer value of the sorted array.

Answer 2

Any sorting based on comparison requires O(n log(n)) comparisons in the middle case, not to mention the worst. For more information on why, see http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list . Thus, sorting without comparison can exceed this lower limit even with your magic data structure.

Mappings not related to comparisons (e.g. radix) are usually designed in such a way that they will not use your data structure, so I don’t think that would change them.

Answer 3

Searching in interpolation requires an operation other than comparison, and therefore cannot be used in sorting. If you can interpolate, you can probably do the numbering operations as a radius, and thus work better than O (n log n), and the magic data structures will help.

Counting sorting sorts by O (n) in your magic structure, which is about the same as any integer sorting algorithm. An interesting and possibly unresolved question is how fast is the fastest parallel sorting algorithm for integers. Given an infinite number of processors (e.g. in a non-deterministic turing machine), I expect you can do better than O (n), but I don't know how much.