# How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

I need to write a sorting algorithm which will sort an array $A[1..n]$, $1 \le i \le n$ such that $A[i] \in \{1,2,..,n^5 \}$, all numbers are positive integers in $\Theta (n)$ time.

The solution must use some combination of radix/counting/bucket sort and possibly select algorithm, it can't use any advanced concepts or structures.

I thought of the following:

0) Convert the numbers into base $n$.

1) Count how many digits each number of the array $A$ contains. We know that the number with max amount of digits will be $n^5$. It'll have $\lfloor{\log_b n^5} \rfloor +1= \lfloor 5\log_b n \rfloor+1$ digits, where $b$ is the base.Because we changed the base to $n$, there will be $\lfloor 5\log_n n \rfloor+1 =6$ unique digit lengths. Create an array countArray which will contain how many occurrences of tens, hundreds etc are.

2) Create subArrays which will contain numbers of the same amount of digits and run radix sort on each such subarray. Radix-Sort runs in $\Theta(d(n+b))$ in general and in our case it will become $\Theta(6(n+n)=\Theta(6n)=\Theta(n)$.

3) In the last step we copy the sorted subarrays into the output array.

Below is the pseudocode but I'm interested if my idea is correct and if the time complexity of my algorithm is $\Theta(n)$:

1 MySort(A, n)                    //A is the array, n is array length
2    uniqueDigitsNum <- 5log_n(n) + 1=6
3    init countArray             // the array of length uniqueDigitsNum
4    for i <- 0 to n             //O(n)
5        //B is a helper array which will store how many digits are in a given number
6        countDigits(A[i], B[i])
7        countArray[B[i]]++      //update the count of how many times we see x digits in CountArray
8    // init a 2d array which will contain uniqueDigitsNum subarrays
9    init subArrays of length uniqueDigitsNum
10    for k <- 0 to uniqueDigitsNum  //O(6)
11        init subArrays[k] of length countArray[k]
12    for k <- 0 to uniqueDigitsNum  //O(6n)
14    //we'll need 'j' to know at which index to start copying the next subarray in the big output array
15    j <- 0
16    for k <- 0 to uniqueDigitsNum  //O(n)
17        for j to countArray[j]     //O(countArray[j])
18            outputArray[j] <- subArrays[k][j]

• What is the context where you encountered this question? Did it come from a textbook? Can you give a full citation? How do you know the problem is solvable? – D.W. May 24 '17 at 20:01
• It's an exercise given in our algorithms class. It is solvable because otherwise they wouldn't give it to us and this is the full citation – Yos May 24 '17 at 20:03
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. May 25 '17 at 17:03
• " I think it'd be appropriate for someone to post an answer which offers the correct solution or correction of my mistakes" -- It'd be helpful to you, but nobody else. Whether it's appropriate (or even legal) depends a lot on your ethics and the rules of your school. – Raphael Aug 23 '17 at 11:29
• For instance, TM vs RAM. If RAM, uniform or logarithmic cost model? Your task may be impossible in one and trivial in the other. You may want to peruse our reference questions. – Raphael Aug 23 '17 at 11:34

1. Radix sort for integers of arbitrary length has $\mathcal{O}(mn)$ time complexity, where m is the length of number.
2. Count digits takes $\mathcal{O}(\log(n))$ time, so, your cycle will take at least (in worst case though) $\mathcal{O}(n \log(n))$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them.
Of course, there exists an algorithm that can sort any array of numbers in $\mathcal{O}(n \log(n))$ time and $O(\log(n))$ space.
• Actually I found a trick that we can convert the numbers to base $n$ which will allow us to achieve linear time complexity if my calculations are correct – Yos May 25 '17 at 7:34
• Line 6, you call that function $n$ times and itself it takes $O(log(n))$ time. – rus9384 May 25 '17 at 13:33
• Why do you think that it's constant? If you'll take $n = 10^6$ you will receive a maximum number $n^5 = 10^{30}$ and it's length is 31 decimal digits (103 bits). If you'll convert that number into base $n$ it'll be represented as 5 24-bit strings. – rus9384 May 25 '17 at 14:30