# How to sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

I need to write an algorithm which will sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

The solution must use hash-tables and advanced data structures including any variation of trees is not allowed.

I thought of the following:

1 Sort(A, n)
2   init B[2][sqrt(n)] //B[1][sqrt(n)] will hold the distinct elements
//B[2][sqrt(n)] will hold the number of occurrences
//of element B[1][k] in the original array A
3   for i<-0 to n
4       hash(A[i]) //the hash function will also update B[2][i] counter
//of occurrences of A[i] in A
5   Quick-Sort(B[1][sqrt(n)]) //quick-sort will also move
//B[2][k] when B[1][k] is moved
//so that they're aligned
6   count<-0    //keeps track of the next location in A
7   for i<-0 to sqrt(n)
8       for j<-0 to B[2][i]
9           A[count]<-B[1][i] //copy the sorted array into the original array
10          count++

In terms of space complexity it looks right to me since we're using $\sqrt n$ additional space for the hash table.

In terms of time complexity I'm running into problems. The quick-sort operation (or according to my understanding any optimal sort for that matter) on line 5 takes $\Theta(\sqrt n \log{\sqrt n})=o(n)$ which is not $\Theta(n)$.

How can I modify the sorting part/algorithm in order to arrive to $\Theta(n)$ complexity?

• I just realized that if the time complexities of other loops in the algorithm are $\Theta(n)$ and the sort is $o(n)$ then it's still $\Theta(n)$ in total. Am I right? – Yos Jun 7 '17 at 19:06
• If you have an $o(n)$ algorithm and want to make it a $\Theta(n)$ algorithm, just add a loop running in time $\Theta(n)$. That said, any sorting algorithm runs in $\Omega(n)$, and indeed your algorithm already runs in time $\Theta(n)$. Moreover, it is pretty stupid to ask you to given an algorithm which performs at least as bad as $\Omega(n)$. Usually we are looking for fast algorithms rather than for slow ones. – Yuval Filmus Jun 7 '17 at 19:13
• Under must you mean it is given as task condition? – rus9384 Jun 7 '17 at 19:46
• Yes it was given – Yos Jun 7 '17 at 19:47
• @YuvalFilmus should I delete the post? I feel like I realized that the algorithm satisfies the conditions already as you mentioned – Yos Jun 7 '17 at 19:48