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 &lt;- 5log_n(n) + 1=6
3    init countArray             // the array of length uniqueDigitsNum
4    for i &lt;- 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 &lt;- 0 to uniqueDigitsNum  //O(6)
11        init subArrays[k] of length countArray[k]
12    for k &lt;- 0 to uniqueDigitsNum  //O(6n)
13        Radix-Sort(subArrays[k])   //O(countArray[k])
14    //we'll need 'j' to know at which index to start copying the next subarray in the big output array
15    j &lt;- 0                      
16    for k &lt;- 0 to uniqueDigitsNum  //O(n)
17        for j to countArray[j]     //O(countArray[j])
18            outputArray[j] &lt;- subArrays[k][j]
Radix sort for integers of arbitrary length has $\mathcal{O}(mn)$ time complexity, where m is the length of number.
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.