Why is strand sort O(n sqrt n) in the average case?

I found strand sort very appealing to sort singly linked lists in constant space, because it is much faster than for example insertion sort.

I see why it is O(n) in the best case (the list is already sorted) and O(n^2) in the worst case (the list is reversely sorted). But why O(n sqrt n) in the average case? If algorithm is not based on bisection and has polynomial best-case and worst-case performance, is the average case just O(n^m), where m is arithmetic mean of best-case's and worst-case's exponents (m = (1 开发者_Go百科+ 2) / 2 = 3/2, O(n sqrt n) = O(n^(3/2)))?

The original reference to Strand sort is http://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 ... according to that, it is O(n^2). Strand sort was presented as a component of J sort, which it claims is O(n lg n). That the average complexity is O(n^2) makes sense since, in random data, half the strands will be of length 1, and O((n/2)^2) = O(n^2).

On the Wikipedia page that you linked to, the average case performance is O(n lg n) with a citation to this Stack Overflow page. Which is weird because nowhere on this page does it say that.

Anyway, to further what Ulrich was saying, average-case analysis is complicated because it has to take into account how the data is represented on average, which is not trivial.

From Wikipedia:

Determining what average input means is difficult, and often that average input has properties which make it difficult to characterise mathematically (consider, for instance, algorithms that are designed to operate on strings of text). Similarly, even when a sensible description of a particular "average case" (which will probably only be applicable for some uses of the algorithm) is possible, they tend to result in more difficult to analyse equations.