3 ms·

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.