7 ms·
I'm surprised that modern implementations don't use something like quicksort, since it has linear space requirements (sorts in-place) and good constants on aver
by andrewstuart2 12y ago
I'm surprised that modern implementations don't use something like quicksort, since it has linear space requirements (sorts in-place) and good constants on average for its n*log2(n) running time.
- irascible 12y agoTimSort is supposed to have better performance on real world datasets.
- gus_massa 12y agoAgree. More info: http://en.wikipedia.org/wiki/Timsort http://en.wikipedia.org/wiki/Timsort The original mail with the proposal is: http://bugs.python.org/file4451/timsort.txt http://bugs.python.org/file4451/timsort.txt
- Arnt 12y agoQuicksort has poor worst-case behaviour, so it's easy to carry out a DoS attack on network services that use it. Language maintainers don't like restricting their library to input from friendly users, at least not when there are other algorithms that work reasonably with unfriendly input.
- jonesetc 12y agoIsn't the malicious attack fought by just picking a random pivot?
- Freaky 12y agoThere are still inputs that will make it go quadratic, that just obscures it slightly. A proper fix is to fall back on a different sort if it looks like quicksort is doing that: https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort
- thaumasiotes 12y ago> There are still inputs that will make it go quadratic Can you elaborate on this? To force quicksort into a quadratic running time, you need to ensure that each pivot splits off a bounded number of elements (e.g. no more than three, or no more than twenty million) from the rest of the list. If the pivot is being chosen at random, then it looks to me like the guarantee you'd need to make is "every single element of this list [because any of them might be chosen] is larger, and smaller, than no more than k other elements of the list". But as the size of the list grows, that condition forces it to be mostly composed of the same element repeated over and over again, which is really easy to sort, and in particular is really easy for quicksort to handle.
- nightcracker 12y agoSee my bug report on libc++: http://llvm.org/bugs/show_bug.cgi?id=20837 http://llvm.org/bugs/show_bug.cgi?id=20837 .
- thaumasiotes 12y agoBut that adversary works by causing the sorting agent to run arbitrary, adversary-supplied code every time it makes a comparison. It has to do that because it invents the values in its list on the fly when it detects them being accessed by the sort (also, in order to detect them being accessed by the sort). That's not really the same thing. I mean, if you want to tie up a process, and you can already make it run arbitrary code that you supply, just give it something like while(1); . If this adversary were forced to realize all the values it fed to the sorter before the sorter did any work, or if it were unable to supply its own code to the sorter, random pivot selection would be a defense. edit: I feel like pointing out that a quicksort implementation could defeat this adversary, without hurting its O(n log n) running time, by just comparing the first element of the sublist it was working with to every other element in the sublist -- and throwing away the results -- and then proceeding as normal. This is O(n) comparisons, which violates the vulnerability criterion of making only O(1) comparisons per call, but doesn't affect the big-O running time at all. What it does do, with an eye to this particular adversary, is realize all the values before doing any sorting work. It still doesn't fix the actual vulnerability the paper identifies, which is that you're running adversary-supplied code. I'm growing to feel like your bug report was frivolous.
- Robin_Message 12y agoPutting a cryptographically secure pseudo-random number generator into a sorting library is a bit awkward, and if it's not a good random number generator, then it's still DoS-able.
- Arnt 12y agoPretend you're the maintainer of OpenJDK. Do you want to go down that road or do you want to change to another algorithm? Remember that randomness can be difficult to find and that the malevolent has a copy of the JDK to use for experiments. Is Quicksort that much better, or do you just change?
- nightcracker 12y agoNo, it is fought by switching to heapsort if the recursion depth exceeds 2*log2(n).
- sbi 12y agoHeapsort has poor cache performance though. Its asymptotic complexity depends on the assumption that memory access is O(1), which is not borne out in practice.
- nightcracker 12y agoThis is true, but the worst case of quicksort is so rare that this does not matter for average performance.
- stonemetal 12y agoOnly if you use a secure random, otherwise you are just obscuring the problem and are still vulnerable.
- rifung 12y agoI don't think so.. If you implement quicksort the way I've normally seen it implemented (elements less than pivot to left, others to right), you could just give the array elements that are all the same value. Then, you would easily get the O(n^2) runtime because your pivot would always be the left most element.
- andrewstuart2 12y agoGot it. That definitely makes sense :-)
- maxlybbert 12y agoIt doesn't have to have poor worst-case behavior: https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pd... (from the author of the Algorithms textbook used at my college).
- ufo 12y agoCorrect me if I'm wrong but I got the impression that prof Sedgewick's slides were about quicksort behaviour when the input has many equal keys. That would still result in quadratic runtime against maliciously crafted input.
- maxlybbert 12y agoI may have oversold Sedgewick's claim: he doesn't actually say that a properly implemented quicksort will never go quadradic; only that "The average number of compares per element ... is always within a constant factor of the entropy" and "No comparison-based algorithm can do better" (page 16). I've never looked into whether a Sedgewick-approved Quicksort can avoid worst case behavior against antiquicksort ( http://www.cs.dartmouth.edu/~doug/aqsort.c http://www.cs.dartmouth.edu/~doug/aqsort.c , http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf ).
- IsTom 12y agoYou can always pick median element in O(n) time and it makes quicksort's worst case be O(nlogn)
- thaumasiotes 12y ago> its n*log2(n) running time If you're going to talk about asymptotic running time, why specify log_2? As soon as you elide a multiplicative constant, all logs are equivalent.
- geophile 12y agoMany years ago, I ran into an intermittent performance problem that was caused by a self-propagating worst case in our quicksort implementation. If you sorted a sequence with one item out of place in an otherwise sorted array, you would get an n-1/1 split, and the pattern would repeat itself on the larger side of the split. We fixed this by picking a pseudo-random pivot, I think.
- masklinn 12y agoTimsort is stable, has an O(n) best case and O(n log n) worst case and has specific optimisations for e.g. partially-sorted sequences. It can also be implemented in-place to reduce space requirements from O(n) to O(log n). > since it has linear space requirements (sorts in-place) Quicksort has a O(log n) worst-case space requirement
- IsTom 12y agoThere is an in-situ quicksort that has the same asymptotic time bounds as the usual kind. It (kind of) encodes stack by shuffling some elements in unsorted data.
- mark-r 12y agoI for one appreciate the fact that it's stable. That has definite benefits sometimes.
- Retra 12y agoThis is making me wonder if there is a theorem that would imply a stable sort on data that doesn't need it would be less efficient than a comparable unstable sort. There has to be a cost for stability, right?
- TheLoneWolfling 12y agoNot in asymtotic terms, at least. There exists a stable sorting algorithm that's O(1) axillary space, and O(n log n) worst-case time - wikisort. As both of those are provable lower bounds, this seems false.
- JanKanis 12y agoTimsort is especially good at reducing the number of comparisons needed by taking advantage of already ordered subsequences in the input. This advantage comes at a cost of more overhead compared to e.g. quicksort. Therefore Timsort is faster if the comparison operations are expensive, quicksort if they are cheap. Java takes advantage of this by using Timsort to sort arrays of objects with a user specified comparison function, and quicksort to sort arrays of primitives. (Or at least it used to.) In Python everything including comparisons is relatively slow so they just use Timsort all the time.
- xxs 12y agoJDK is using quicksort (more like variation of) for sorting primitives. (being not stable doesn't matter for primitives)