2

Let's say that you are given an integer array A of size n. You know in advance that O(√n) elements of A can be larger than 2020(n)^(5) − 5n, and the remaining elements of A are in the range [1, 2020n^5 − 5n]. It turns out that, in this case, A can be sorted in O(n) time in the worst case.

I am trying to solve this interesting algorithm question and my intuition is to use radix sort as part of my solution. The part that stumps me is the O(√n) runtime, so any pointers in finding such an algorithm would be greatly appreciated!

Improve this question

1 Answer 1

Reset to default
4

Separate the in-range elements from the out-of-range elements (O(n)). Radix sort in the in-range elements (base n; this takes six passes for n ≥ 2020 and is O(n)). Insertion sort the out-of-range elements (there are √n of these, hence O(√n²) = O(n)). Merge the two sorted arrays (O(n)).

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

6 Comments

how do I ensure that this will run in O(n) time in the worst case? Wouldn't doing radix sort and then insertion sort lead to a slower worst case running algorithm?
You're only doing insertion sort on O(√n) elements, so the insertion sort only contributes O((√n)^2) = O(n) to the running time.
Worth mentioning that you have to radix sort the small elements in base n? Any fixed base size results in O(n log n) time.
Oh ok, thank you that makes so much sense! I think I am able to code this up now!
Hmm, how do you know it will be 6 passes?
|

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.