On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei Alexandrescu
wrote:
Another approach I wanted to try was to choose the median of K
with K increasing with the size of the array. This is because a
good pivot is more important for large arrays than for small
arrays. As such, a possibility would be to simply sort a stride
of the input (std.range.stride is random access and can be
sorted right away without any particular implementation effort)
and then choose the middle of the stride as the pivot.
If anyone has the time and inclination, have at it!
Perhaps a "median of log n" is in order, but the trouble is
finding an algorithm for picking the median from n elements. The
so called "median of medians" algorithm can choose a pivot within
30-70% of the range of the median. Otherwise, there doesn't seem
to be any algorithm for choosing the absolute median other than,
say, an insertion sort.
I came up with this clever little guy a while ago which I used in
my implementation of quick sort: http://dpaste.dzfl.pl/b85e7ad8
I would love to enhance it to work on a variable number of
elements, but from what I can comprehend, the result is
essentially a partial heap sort.
