Why in the middle case is the type strand n (n sqrt n)?

Question

I found the strand type very attractive for sorting simply linked lists in constant space, because it is much faster than, for example, sorting an insert.

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 sorted in reverse order). But why is O(n sqrt n) in the middle case? If the algorithm is not based on half-division and has polynomial indicators of the best and worst cases, this is the average case only O(n^m) , where m is the arithmetic mean of the indicators of the best case and the worst case ( m = (1 + 2) / 2 = 3/2 , O(n sqrt n) = O(n^(3/2)) )?

Answer 1

The original Strand sort link is http://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 ... according to this, this is O (n ^ 2). The Strand variety was introduced as a J-type component, which, according to its statement, is equal to O (n lg n). The fact that the average complexity O (n ^ 2) makes sense, since in random data half of the strands will have a length of 1, and O ((n / 2) ^ 2) = O (n ^ 2).

Answer 2

On the Wikipedia page you contacted, the average case performance is O (n lg n) with a link to this page. Which is strange because nowhere on this page is it said.

In any case, in the future, what Ulrich said, the analysis of the average size is complicated, since it must take into account how the data are presented on average, which is not trivial.

Material from Wikipedia:

Determine which medium input tool is difficult, and often this average input has properties that make the mathematical description difficult (consider, for example, algorithms that are designed to work with lines of text). Similarly, even if a reasonable description of a particular “middle case” (which is likely to be applicable only to some applications of the algorithm), it can lead to a more complex analysis of the equations.