D-Programming-Language/phobos — pull request #1735 by Xinok (2013-11-29 01:46:20+00:00)
Title: Fix issue 7767 - wost case of quick sort

The unstable sort in std.algorithm is currently implemented as quick sort. There are many cases which cause it to run in quadratic time. This has security implications and can result in a DoS attack.

This pull request resolves the problem by implementing heap sort as a fall-back algorithm, effectively changing it into an intro-sort. This will guarantee that the unstable sort runs in O(n log n) time in the worst-case.

I would like to discuss a couple other improvements I can implement as well:
- Replacing the [linear] insertion sort with a binary insertion sort.
- Choosing the pivot from a median of five in exactly six comparisons.

Both changes do add overhead and benchmarks showed a 10-15% loss in performance in an ideal case, but a comparable gain is made in reducing the number of comparisons (i.e. predicate calls).

Relevant discussion: http://forum.dlang.org/thread/prkthuzsmbppjltvohdh@forum.dlang.org
Bug report: http://d.puremagic.com/issues/show_bug.cgi?id=7767