On Sunday, 17 November 2013 at 01:07:20 UTC, Ivan Kazmenko wrote:
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.
Woah, that sounds complicated. Not 100% sure I entirely
understand but it seems to rely on changing the elements while
you sort. How would that work in real life?
For example, how would this defeat the following pivoting method.
1. Find the median value in the array. This can be done
deterministically in linear time, so from a theoretical point of
view is just as fast as picking a random element since you use
linear time.
2. Use that as the pivot.
