On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote: > I believe the best approach is to switch qsort.c to "introsort". > The changes are minimal and the elimination of the O(n^2) worst > case is compelling.
I've added input arrays to the qsort regress test that exhibit quadratic behavior in our quicksort. The introsort diff prevents qsort from going quadratic. McIlroy's "A Killer Adversary for Quicksort" was used to generate the test vectors. http://www.cs.dartmouth.edu/~doug/mdmspe.pdf - todd
