An O(n log sqrt(n)) sorting algorithm? Skiena TADM 2nd Question 4-28 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?
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.