[Jabbles]

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

[mzs]

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

[mattchamb]

This is the same approach used the the .NET framework in Array.Sort: http://referencesource.microsoft.com/#mscorlib/system/collec...

You can see the fallback to heapsort here: http://referencesource.microsoft.com/#mscorlib/system/collec...

[lelf]

Huh? And by what black magic its qsort is not O(n^2) (worst)?

[bcoates]

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

[chowells]

Well, 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)