4 ms·
In comparison, the Go standard sort function is not vulnerable to this, and references the same paper as this article: http://golang.org/src/pkg/sort/sort.go#L
by Jabbles 12y ago
In comparison, the Go standard sort function is not vulnerable to this, and references the same paper as this article:
http://golang.org/src/pkg/sort/sort.go#L168 http://golang.org/src/pkg/sort/sort.go#L168
- mzs 12y agoI don't see it, seems just a median of three quick sort - the median of three for the partition selection is to mitigate poor performance of quick sort on sorted and reverse sorted inputs. edit: I'm an idiot, totally glossed-over the switch to heap sort logic.
- lelf 12y agoHuh? And by what black magic its qsort is not O(n^2) (worst)?
- chowells 12y agoWell, Tarjan developed an O(n) worst-case order statistics algorithm, which you could use to implement exact pivot selection and partitioning in O(n) time. The constant factors would be horrid, but it would be a valid implementation of quicksort with a worst-case running time of O(n log n)
- bcoates 12y agoIt sets a stack limit proportional to log(n) and gives up and heapsorts the subproblem if the limit is exceeded. You get no more than n log(n) quicksort operations, plus heapsorting any partition of the input which is also n log(n) In other words, they use the worst-case n log(n) heapsort with an optimization to use the much faster quicksort for non-pathological inputs, which is almost always.
- mattchamb 12y agoThis is the same approach used the the .NET framework in Array.Sort: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/arraysorthelper.cs#300 http://referencesource.microsoft.com/#mscorlib/system/collec... You can see the fallback to heapsort here: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/arraysorthelper.cs#335 http://referencesource.microsoft.com/#mscorlib/system/collec...