News for hackers. Stuff that matters.

A comment on On the Worst-Case Complexity of TimSort. Parent comment

Re:On the Worst-Case Complexity of TimSort by Fri31Aug on Friday August 31, 2018 @04:18AM (#17883840)
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.
[ Parent | on HN ]
Re:On the Worst-Case Complexity of TimSort by pxndx on Friday August 31, 2018 @04:28AM (#17883883)
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).
[ Parent | on HN ]
Re:On the Worst-Case Complexity of TimSort by Fri31Aug on Friday August 31, 2018 @05:59AM (#17884262)
Ah I didn't know it also exploited reversed runs. Amazing.
[ Parent | on HN ]