Radix sort algorithm with O(n) worst case

user_15236657 0
Viewed 138

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!

radix-sort big-o sorting algorithm
1 Answers

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)).

user_21446690
Related