51–60 of 78 posts
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).
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.
This is wrong. See https://en.m.wikipedia.org/wiki/Quicksort , section "Selection-based pivoting".
https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
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 :)
Earlier quoted context omitted.
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.
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–…
Earlier quoted context omitted.
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.
Worst-case complexity.
Also, I needed to bump my JVM heap up to 16GB (not 9GB as recommended), just to run it.
Earlier quoted context omitted.
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–…
Out of curiosity, what do you read/follow that makes stuff like this discoverable?
So, uh, I guess I just work with the right people :) Sorry that I can't give you anything concrete. All of these papers were presented at ESA (European Symposium on Algorithms), though, so that's a good venue to follow. But beware, ESA has a theory track that's a lot bigger than the experimental track, and papers published there can be somewhat unapproachable ;)
Earlier quoted context omitted.
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–…
Out of curiosity, what do you read/follow that makes stuff like this discoverable?
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
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.
For instance, timsort is also very fast if only a single element is unsorted, or only two elements, or only three elements. These are not special cases explicitly handled, its just the natural way the algorithm works.