6

Suppose that you have a magic data structure that represents a linear sequence of elements that supports lookup, insertion, and deletion of any index 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(n2) 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.)

Improve this question
2
  • 3
    If I was allowed to use magic data structures, I'd use one that was always pre-sorted. Then sorting would be a O(1) operation. Commented May 12, 2011 at 5:28
  • This question appears to be off-topic because it is about a theoretical CS construct, not a practical programming problem. Commented Nov 8, 2013 at 15:54

3 Answers 3

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I'm not sure I see how counting sort can be made to run in O(n) time with this data structure. Counting sort takes O(n + U) time, where U is the size of the universe of elements being sorted, and I don't see how a magic array can eliminate the U term. Can you elaborate on this?
@templatetypedef We can eliminate U term, if we will use counting sort in combination with radix sort (we can do it, because counting sort is stable sort).
4

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.