On Sunday, 17 November 2013 at 00:18:24 UTC, Chris Cain wrote:
I think it's more complicated than that. Let's assume for a
moment that you've proven that such an unstable sort must exist
that is faster (I'm not convinced that it necessarily must take
extra work to maintain stability). You have not shown how much
faster it might be (it could be only 1% faster) nor how much
work it would take to discover (even an ideal pivot choice for
quicksort actually cannot be as fast as Timsort on an already
sorted sequence, and quicksort is not an appropriate algorithm
for accepting presorted subsequences). If it takes 2 years to
come up with an unstable sort faster than Timsort, then it
seems like a long time to be using something that isn't the
best that we currently have. Especially if D is to be used in
benchmarks against other languages.
Regarding an ideal pivot choice for quicksort, I'd like to
emphasize that it is simply non-existent. Here's why.
Let us measure quicksort performance as the number of comparisons
it makes.
Let us make some assumptions:
quicksort goes as
--(1) choose a pivot p in O(1) comparisons;
--(2) partition the segment into two;
--(3) run quicksort recursively on the two resulting segments.
Now, (2) is effectively done by comparing every element with p,
thus in Theta(n) (on the order of n) comparisons where n is the
length of the current segment.
Under these assumptions, we can construct the killer array for an
arbitrary quicksort of such kind, even if we don't know how
exactly the pivot is chosen (say, closed source or obfuscation),
but we have the following interface to it:
Instead of accessing the array a[], quicksort calls the function
less(i,j) which tells it whether a[i]<a[j], and we control that
function.
Now, we start with all values in array a[] undefined. With each
a[i], we associate a counter c[i]: how many times it took part in
a comparison. As we can see from the above, during a single call
to quicksort, in steps (1) and (2) the pivot will eventually get
Theta(n) comparisons, while other elements will all get only O(1)
comparisons each.
So here's what we'll do.
1. When a comparison asks to relate two undefined values, we pick
one of them with the larger c[i] and make it the lowest number
possible. That is, the first fixed value will be 0, the next 1,
and so on. (In the end, a[] will be a permutation of 0, 1, ...,
n-1.)
2. When we are asked to relate a defined value to an undefined
one, the defined value will always be lower (because, when we
eventually define the undefined one, it will be higher than all
the values defined before it).
3. When we are asked about two known values, just tell the truth.
This simple algorithm ensures that, on each call to quicksort, we
quickly fix the pivot as one of the O(1) lowest values on the
segment. So, one of the next two segments will have length
n-O(1), and the recursion gives us Theta(n) segments of linearly
decreasing lengths, and thus Theta(n^2) total running time.
Now, the assumption of picking a pivot in O(1) comparisons covers
a broad variety of pivot choices, including
first/last/middle/random element, median of three or five, median
of medians, or any combination of these. The random pick fails
in the following sense: if we seed the RNG, construct a killer
case, and then start with the same seed, we get Theta(n^2)
behavior reproduced.
Double-pivot quicksort can be forced to go quadratic in a similar
fashion.
Now, introsort escapes this fate by switching to a
guaranteed-n-log-n algorithm instead of (3) when it goes too
deep. This comes at a (small) cost of checking the current depth
on every call to quicksort.
The above is just my retelling of a great short article "A Killer
Adversary for Quicksort" by M. D. McIlroy here:
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
Ivan Kazmenko.
