Hacker News Reader

Comment by matharmin | Hacker News Reader

In the worst case, rho is equal to n, and you get O(n log n). However, O(n + n log rho) gives a better description of how it performs on partially sorted arrays.

View on HN

And in the best case (already sorted array), it's equal to 1 and the algorithm performs as O(n), which is nice to prove in one go.

In some other typical cases (otherwise sorted array with one element inserted, two sorted arrays appended to each other) rho is 3 and 2, so also O(n).

All sorting algorithms can trivially be made to perform in O(n) in the "already sorted" scenario without worsening the worst case complexity, so that isn't really helpful.

It can be done only by adding an initial check that does only that. But this means that the algorithm speed doesn’t gradually increase with partially sorted sequences.

For instance, timsort is also very fast if only a single element is unsorted, or only two elements, or only three elements. These are not special cases explicitly handled, its just the natural way the algorithm works.

Nitpick: \rho = n/2 in the worst case, if n > 1, but that still gives you O(n log n).

Why n/2? If the array is, for example, sorted in the reverse order, then there is no monotonous run at all, in which case I believe the algorithm considers each element from the array being a run in itself, giving n runs.

Runs can be increasing or decreasing, a reversed array is a single run. Worst case is n/2 because you can always split the array in pairs (if it alternates a high and a low value for example).

Ah I didn't know it also exploited reversed runs. Amazing.

Exactly. Sometimes those are called "adaptive algorithms", in the sense that the complexity depends on some properties of the input, so even though the worst case complexity is still O(n log n), for many outputs it will do much better.

Reply on news.ycombinator.com