# Sorting n elements in worst case of $\sqrt{n}\log n$

Can $$n$$ elements be sorted in a worst case time of $$\sqrt{n}\log n$$? Why or why not? I've seen algorithms being sorted in the worst case of $$n\log n$$, so why can they be or cannot be sorted in $$\sqrt{n}\log n$$?

• Depend on the data. See counting sort – kelalaka Nov 25 '18 at 18:13
• Without any assumptions on the data, any comparison based sorting algorithm takes $\Omega(n \log n)$. See here – Gokul Nov 25 '18 at 18:15
• Have you consulted a textbook, or any reputable resource about it? What makes you think about $\sqrt(n)$, specifically? – Raphael Nov 25 '18 at 19:07

This is impossible. You cannot sort $$n$$ elements without examining each element at least once, which takes at least $$n$$ operations.
$$n=\sqrt{n}\cdot\sqrt{n}\ge\sqrt{n}\cdot\log{n}$$ for all $$n>1$$, assuming the logarithmic base is at least 2. (Of course, if you assume something completely asinine like $$\log_{1.000001}n$$, it would be technically possible for some values of $$n$$.)