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?
