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 A3   for i<-0 to n4       hash(A[i]) //the hash function will also update B[2][i] counter                   //of occurrences of A[i] in A5   Quick-Sort(B[1][sqrt(n)]) //quick-sort will also move                                  //B[2][k] when B[1][k] is moved                                  //so that they're aligned6   count<-0    //keeps track of the next location in A7   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 array10          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?
How to sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?
algorithms;sorting;hash tables