Live data from Hacker News

On the Worst-Case Complexity of TimSort

drops.dagstuhl.de

31–40 of 78 posts

Re: On the Worst-Case Complexity of TimSort

#31
post #27
post #2

Not good that Java's sort still has bugs.

I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.

The java bug (https://bugs.openjdk.java.net/browse/JDK-8203864) has some more information on the history, including a reference to an earlier paper from 2015 relating to the same problem.

Apparently, the earlier paper had an error, so the implemented fix was not complete.

Still intriguing, though!

Re: On the Worst-Case Complexity of TimSort

#32

Earlier quoted context omitted.

Right, like how Quicksort can be pretty different depending on how you choose the pivot. It's still Quicksort, but there's different variants.

yes but they will share the same complexity

You can make the average-case perform in O(n^2) by always pivoting on the smallest number in the array. Nobody would do _that_, but it shows that pivot choice can affect complexity.

Ergo, computer scientists researching the algorithm mathematically must consider the effect of choice of pivot.

Re: On the Worst-Case Complexity of TimSort

#33

Earlier quoted context omitted.

Right, like how Quicksort can be pretty different depending on how you choose the pivot. It's still Quicksort, but there's different variants.

yes but they will share the same complexity

Depending on how you choose the pivot, the worst-case of complexity of Quicksort can be O(n^2) or O(n log n)

Re: On the Worst-Case Complexity of TimSort

#35
post #27
post #2

Not good that Java's sort still has bugs.

I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.

It looks deceptively like it but 'kudos' is not plural of a kudo (or reference to some awesome thing Kudo once did).

Re: On the Worst-Case Complexity of TimSort

#36
post #26

Earlier quoted context omitted.

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.

Re: On the Worst-Case Complexity of TimSort

#37
post #27
post #2

Not good that Java's sort still has bugs.

I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.

What's amazing is how little understanding we seem to have over such critical widely-used code. Java opted for a complex and arguably unproven algorithm, so it was always a risk. We now have functional languages that are able to express provably correct sorting algorithms, so the bar is getting higher.

Re: On the Worst-Case Complexity of TimSort

#38

Earlier quoted context omitted.

yes but they will share the same complexity

Depending on how you choose the pivot, the worst-case of complexity of Quicksort can be O(n^2) or O(n log n)

No, worst-case complexity of real quicksort is always O(n^2), regardless of pivot choice strategy (even with stochastic pivot choice, although you’d have to get very unlucky to hit that worst case). You can make the average case better or worse though.

The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.

Re: On the Worst-Case Complexity of TimSort

#39
post #35
post #27

Earlier quoted context omitted.

I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.

It looks deceptively like it but 'kudos' is not plural of a kudo (or reference to some awesome thing Kudo once did).

… and even if it were a plural the apostrophe would be misplaced.

Re: On the Worst-Case Complexity of TimSort

#40

Amazing there is still something to find in a sort algorithm.

Especially when targeting realistic machine models, there are a lot of things that are suboptimal about the classical sorting algorithms like quicksort or mergesort. For example, a quicksort with perfect choice of pivot will incur a branch miss with probability 50% for every element. That's not something classical complexity analysis measures, but on actual CPUs, branch misses have quite an impact (something like 10–15 cycles). Shameless plug for something I once built for a lecture to demonstrate this: https://github.com/lorenzhs/quicksort-pivot-imbalance

For sorting algorithms that take the behaviour of modern CPUs into account, check out ips4o (https://arxiv.org/abs/1705.02257, code: https://github.com/SaschaWitt/ips4o) or for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (https://arxiv.org/abs/1604.06697, code: https://github.com/weissan/BlockQuicksort). Note that both papers were published in the last two years :)

Of course these algorithms are much more complex and error-prone to implement and use some additional memory, which may explain why they're not used in standard library implementations of popular languages.

Post reply on HN