-2
$\begingroup$

If I have n integers, which are in range 1 to n^2, should I use count sort? My thought is that I shouldn't because it would be a risk if n happens to be substantial. I can't seem to figure out the implication on the time complexity for this problem, so I can't prove anything. Anybody have any insights?

$\endgroup$
5
$\begingroup$

Since count sort is $O(k+n)$ (Analysis of count sort) as pointed out by D.W., for worst case input count sort will be more efficient than $O(n\log n )$ sorting algorithms as long as $k = o(n \log n)$.

Since in your case $k$ is $n^2$. i.e. $k = \omega(n \log n)$, it will be better to use $O(n \log n)$ sorting algorithms, or you can even use quick sort (for better overall average case efficiency).

| cite | improve this answer | |
$\endgroup$

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