3
$\begingroup$

Skiena writes:

In one of my research papers [Ski88], I discovered a comparison-based sorting algorithm that runs in $O(n\log\sqrt{n})$. Given the existence of an $\Omega(n \log n)$ lower bound for sorting, how can this be possible?

I believe the research paper he is referring to is Encroaching lists as a measure of presortedness, and the $O(n\log\sqrt{n})$ algorithm is Melsort. I don't have the full text of the article, but the abstract states that melsort has [time] complexity $O(n\log m)$, where $m$ is the number of "encroaching lists" present in the input and $n$ is (presumably) the size of the input.

I suspect that the solution to Skiena's apparent paradox hinges on expected running time vs worst case running time. He notes in the abstract of the '88 paper that melsort is "linear for well ordered sets and reduces to mergesort and $O(n\log{n})$ in the worst case." If the expected number of encroaching lists, $m$, is $\sqrt{n}$ (as apparently conjectured by Skiena, according to wolfram's article on encroaching lists), it would follow that melsort's expected runtime is $O(n\log\sqrt{n})$.

But wikipedia states that "A comparison sort must have an average-case lower bound of $\Omega(n \log n)$ comparison operations," citing Cormen et al. Checking the referenced pages of Introduction to Algorithms, I see only a proof that the worst-case runtime has that bound. Is the Wikipedia article incorrect?

$\endgroup$
  • $\begingroup$ Sorry, maybe I am missing something, but isn't $\log\sqrt{n}=\frac{\log n}{2}$? $\endgroup$ – drzbir Dec 27 '16 at 16:37
  • $\begingroup$ Of course! Sometimes you miss the simple things. Yes, I think you're right - there is only a constant factor's difference between $\log\sqrt{n}$ and $\log n$, so they are asymptotically equivalent. $\endgroup$ – Chad Dec 27 '16 at 16:52
5
$\begingroup$

Azzo is correct. It's very simple:

$n\log \sqrt{n} = n\log n^{\frac{1}{2}} = \frac{1}{2}n\log n = \Omega (n\log n)$

Therefore Skiena's $O(n\log\sqrt{n})$ sorting algorithm does not violate the lower bound on comparison sorts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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