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 + 2) / 2 = 3/2, O(n sqrt n) = O(n^(3/2)))?
Jim Balter :
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).",
2011-02-08T03:17:19