Hacker News Reader

Comment by grillorafael | Hacker News Reader

Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n?

Memories on the subject are not great so might be saying bullshit in here

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.

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.

It shouldn't be called n because then `n log n` and `n log m` convey different meanings. In the first case, `n` is one and the same variable, where in the second, `n` and `m` are independent of each other.

You can call it `m` or `rho` or whatever, just use a different variable.

Here, ρ is not independent of n, though

Rho is always 1 to n as defined.

In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.

It sort of is though. You can have a really large N with rho = 1, just like you can have a really small N with rho=N. They're orthogonal variables, and they both impact the run time.

n varies with the input as well :) But yes, since ρ is bounded by n you can reduce the complexity to O(n log n) again, but i think the important part here is to distinguish the complexity against other sorting algorithms and Timsort improves things for specific inputs as they note.

Reply on news.ycombinator.com