Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]

I will need to write an algorithm that sorts that array in $\Theta$($n$)

Furthermore, will the same mission could be performed if, now it is given that except from $n/2$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]

And how about $n/log(n)$ ( lower value )? ( In this time thare are ( $n$ - $n/log(n)$ ) ( lower value ) integers in the given bounds )

Note - We can not know where are the the integers located in the array

MY METHOD: For the first question I tried to seperate the array to 2 arrays, and then for the array with the numbers inside the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$] - I have converted the elements to $n$ based and sorted it with counting-sort. For the second array - sort it with any other sorting method and then merge the 2 arrays

My questions are:

  1. Does my approach is correct to the first question ( in terms of run-time, algorithm )?
  2. What would be the best solution for the other question asked
  • $\begingroup$ I have seen this similar question at least 4 times this month. :/ (just saying. Not directed towards OP) $\endgroup$ – Inuyasha Yagami May 16 at 12:53
  1. I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size $(n-1)\sqrt{n}$ to count, so you would be in $\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here.

  2. It is not possible to sort in $O(n)$ for one of the other bounds. Indeed, the problematic part would be sorting values not in the bounds $[\sqrt{n}, n\sqrt{n}]$: sorting $\frac{n}{2}$ values requires $\Omega(n\log n)$ time.

    On the other hand, sorting $\frac{n}{\log n}$ values can be done in $O\left(\frac{n}{\log n}\log\left(\frac{n}{\log n}\right)\right) = O(n)$ time.

  • $\begingroup$ For the second one: I we will use linear-sorting method in order to sort $n/2$ values? $\endgroup$ – Omri Braha May 17 at 18:33
  • 1
    $\begingroup$ If you have no particular hypothesis on those values, you cannot guarantee that they can be sorted in linear time. $\endgroup$ – Nathaniel May 17 at 18:35
  • $\begingroup$ Thank you, and for the last, $O\left(\frac{n}{\log n}\log\left(\frac{n}{\log n}\right)\right) = O(n)$ how is it possible? I have tried to solve it by logarithm laws .... $\endgroup$ – Omri Braha May 17 at 18:49
  • 1
    $\begingroup$ $\log\left(\frac{n}{\log n}\right) = \log(n) - \log \log n \leq \log n$ $\endgroup$ – Nathaniel May 17 at 18:50
  • $\begingroup$ Thank you again! $\endgroup$ – Omri Braha May 17 at 18:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.