Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

On the Worst-Case Complexity of TimSort

drops.dagstuhl.de

Post reply on HN
Print view View original

21–30 of 78 posts

Re: On the Worst-Case Complexity of TimSort

#21

Post by ehsankia »

brazzy wrote: post #16
grillorafael wrote: post #10

Earlier quoted context omitted.

Yes. If the java have a different complexity it is a different algorithm. To the writers defense, they have to algorithm in pseudo code in the article

> If the java have a different complexity it is a different algorithm. It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.

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

Re: On the Worst-Case Complexity of TimSort

#22

Post by ehsankia »

ygra wrote: post #11
phoe-krk wrote: post #5

Earlier quoted context omitted.

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

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.

Re: On the Worst-Case Complexity of TimSort

#23

Post by sleepychu »

0x0 wrote: post #17

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)

Crashing out of execution doesn't really seem like an actionable attack vector, unless that exception bubbles all the way to the application invocation.

Re: On the Worst-Case Complexity of TimSort

#24

Post by Fri31Aug »

pmiller2 wrote: post #19
matharmin wrote: post #7

Earlier quoted context omitted.

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.

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.

Re: On the Worst-Case Complexity of TimSort

#25

Post by Insanity »

0x0 wrote: post #17

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)

Chances are you'll get an OutOfMemoryException first :)

Re: On the Worst-Case Complexity of TimSort

#26

Post by pxndx »

Fri31Aug wrote: post #24
pmiller2 wrote: post #19

Earlier quoted context omitted.

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

Re: On the Worst-Case Complexity of TimSort

#27

Post by wiz21c »

willtim wrote: 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.

Re: On the Worst-Case Complexity of TimSort

#28

Post by grillorafael »

ehsankia wrote: post #21
brazzy wrote: post #16

Earlier quoted context omitted.

> If the java have a different complexity it is a different algorithm. It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.

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

Re: On the Worst-Case Complexity of TimSort

#29

Post by elygre »

0x0 wrote: post #17

The linked java test file, http://igm.univ-mlv.fr/~pivoteau/Timsort/Test.java - still crashes the latest Java 10.0.2 with an 'Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49'. Amazing! I wonder if this makes some web services vulnerable.. if the user can submit a just-so array of ints to be sorted? But it does seem like it would require uploading a really huge array (>4GB?)

This look like https://bugs.openjdk.java.net/browse/JDK-8203864, which has the following additional information:

"While working on a proper complexity analysis of the algorithm, we realised that there was an error in the last paper reporting such a bug (http://envisage-project.eu/wp-content/uploads/2015/02/sortin...). This implies that the correction implemented in the Java source code (changing Timsort stack size) is wrong and that it is still possible to make it break. This is explained in full details in our analysis: https://arxiv.org/pdf/1805.08612.pdf"

Re: On the Worst-Case Complexity of TimSort

#30

Post by masklinn »

TeMPOraL wrote: post #4

How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?

From TFA's introduction:

> there are actually not one, but two main versions of TimSort. The first version of the algorithm contained a flaw, which was spotted in [5]: while the input was correctly sorted, the algorithm did not behave as announced (because of a broken invariant). This was discovered by De Gouw and his co-authors while trying to prove formally the correctness of TimSort. They proposed a simple way to patch the algorithm, which was quickly adopted in Python, leading to what we consider to be the real TimSort. This is the one we analyze in Sections 3 and 4. On the contrary, Java developers chose to stick with the first version of TimSort, and adjusted some tuning values (which depend on the broken invariant; this is explained in Sections 2 and 5) to prevent the bug exposed by [5]. Motivated by its use in Java, we explain in Section 5 how, at the expense of very complicated technical details, the elegant proofs of the Python version can be twisted to prove the same results for this older version.

[5] Stijn De Gouw, Jurriaan Rot, Frank S de Boer, Richard Bubel, and Reiner Hähnle. Open- JDK’s Java.utils.Collection.sort() is broken: The good, the bad and the worst case. In International Conference on Computer Aided Verification, pages 273–289. Springer, 2015.

Post reply on HN