On the Worst-Case Complexity of TimSort • Hacker News Board

Re: On the Worst-Case Complexity of TimSort

#41

Post by iCannotEven » Fri, Aug 31, 2018, 12:06 PM UTC

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

  arrayToSort[sum] = 1;

This is just blatant programmer error. The code is attempting to assign a value to a slot in an array of a fixed size, which does not exist.

Use:

  Integer[] arrayToSort = new Integer[2000000000];

No error.

Re: On the Worst-Case Complexity of TimSort

#42

Post by PL_kolek » Fri, Aug 31, 2018, 12:09 PM UTC

klmr wrote: post #38

FreeFull wrote: post #33

Earlier quoted context omitted.

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.

Isn't there a linear time median selection algorithm, which allows you to always select a pivot in the middle of the sorted part and create two equal halves? This produces a worst-case O(n log n) quick sort, which is no longer quick due to the big constant hidden in O notation.

Re: On the Worst-Case Complexity of TimSort

#43

Post by dmurray » Fri, Aug 31, 2018, 12:34 PM UTC

Scarblac wrote: post #12

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.

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

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.

Re: On the Worst-Case Complexity of TimSort

#44

Post by toxik » Fri, Aug 31, 2018, 12:53 PM UTC

iCannotEven wrote: post #41

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

arrayToSort[sum] = 1; This is just blatant programmer error. The code is attempting to assign a value to a slot in an array of a fixed size, which does not exist. Use: Integer[] arrayToSort = new Integer[2000000000]; No error.

The equivalent Python code works fine, though.

    >>> a=[0]*sum(rls)
    >>> sum=-1
    >>> for i in rls:
    ...   sum += i
    ...   a[sum] = 1
    ... 
    >>> a.sort()
    >>>

Takes a real good while, too.

Re: On the Worst-Case Complexity of TimSort

#45

Post by comicjk » Fri, Aug 31, 2018, 1:12 PM UTC

julienfr112 wrote: post #15

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

Example of the crazy optimizations that apply here: I once got a 20% speedup in a standard recursive search algorithm by abandoning the native function call stack and making my own search-specific stack data structure. Since these algorithms call the same function over and over, making the call stack do minimum work is actually significant.

Re: On the Worst-Case Complexity of TimSort

#46

Post by andrewla » Fri, Aug 31, 2018, 1:20 PM UTC

elygre wrote: post #29

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…

That is not additional information. That bug was created by the authors of this post, and the link is a reference to the exact paper linked to in this post.

Re: On the Worst-Case Complexity of TimSort

#47

Post by nh2 » Fri, Aug 31, 2018, 1:26 PM UTC

klmr wrote: post #38

FreeFull wrote: post #33

Earlier quoted context omitted.

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.

This is wrong.

See https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".

Re: On the Worst-Case Complexity of TimSort

#48

Post by nh2 » Fri, Aug 31, 2018, 1:30 PM UTC

PL_kolek wrote: post #42

klmr wrote: post #38

Earlier quoted context omitted.

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.

Isn't there a linear time median selection algorithm, which allows you to always select a pivot in the middle of the sorted part and create two equal halves? This produces a worst-case O(n log n) quick sort, which is no longer quick due to the big constant hidden in O notation.

Correct, Quicksort with Quickselect for pivot choice.

Re: On the Worst-Case Complexity of TimSort

#49

Post by rthomas6 » Fri, Aug 31, 2018, 1:31 PM UTC

lorenzhs wrote: post #40

julienfr112 wrote: post #15

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–…

This is awesome!

Re: On the Worst-Case Complexity of TimSort

#50

Post by mcherm » Fri, Aug 31, 2018, 1:53 PM UTC

sleepychu wrote: post #23

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.

Causing a crash is an excellent vector for a denial-of-service attack.