3 ms·

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

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.

pmiller2 8y ago
Nitpick: \rho = n/2 in the worst case, if n > 1, but that still gives you O(n log n).
- Fri31Aug 8y ago
  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.
  - pxndx 8y ago
    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).
    - Fri31Aug 8y ago
      Ah I didn't know it also exploited reversed runs. Amazing.
pelario 8y ago
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.
Scarblac 8y ago
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).
- dmurray 8y ago
  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.
  - giovannibajo1 8y ago
    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.

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.

pmiller2 8y ago

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

Fri31Aug 8y ago
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.
- pxndx 8y ago
  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).
  - Fri31Aug 8y ago
    Ah I didn't know it also exploited reversed runs. Amazing.

pelario 8y ago

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.

Scarblac 8y ago

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).

dmurray 8y ago
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.
- giovannibajo1 8y ago
  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.