Dual-Pivot Quicksort and Sorting classes: introspective sort
Jeff Hain
jeffhain at rocketmail.com
Thu Sep 16 13:33:20 UTC 2010
Hello.
I talked with Vladimir about using introspective sort along with the new
dual-pivot quicksort,
but it's maybe worth to bring this discussions into this list (as Vladimir
advised me):
The idea of introspective sort (David Musser, 1997) is to use the usual quick
sort + insertion sort combo,
unless quick sort goes quadratic, in which case remaining sorting is done using
a sort that is O(N*log(N))
in worst case.
Insertion sort is therefore O(N*log(N)) in worst case, which might be needed by
some applications
(if you want to be sure that treatments won't hand for too long, or that if
treatments hang, it's not due
to sorting, to reduce investigations possibilities).
The determination whether quick sort "goes quadratic" or not, can be done very
simply,
using an int "maxDepth" variable, initialized with some value proportional to
the logarithm of
initial sort range width, and decremented on each quick sort recursion : when
this value
reaches zero, i.e. when quick sort did too many recursions, remaining sorting is
done with
the O(N*log(N))-in-worst-case backup sort, instead of partitioning again with
quick sort.
For some sorting range widths (50 ? 100 ?), it might not be worth to bother with
these
anti-quadratic considerations: in that cases, non-introspective sort could be
used,
or introspective sort using Integer.MAX_VALUE as "maxDepth".
I think heap sort is a good O(N*log(N)) backup sort, because unlike merge sort,
it does not require the creation of a new array, which could cause problem in
case
this array would be huge (all we ask to this backup sort is to finish the
sorting not
quadratically, and not to possibly add more trouble by messing up with memory,
even though it could be a tad faster in some cases with latest garbage
collectors).
Summary:
Introspective sort cost:
- have to initialize a counter using a logarithmic or
optimized-pseudo-logarithmic method,
- have to decrement and check the counter at each quick sort recursion,
- have to implement heap sort for use when quick sort goes quadratic.
Introspective sort benefit:
- O(N*log(N)) in worst case, while almost as fast as non-introspective sort in
general case.
Regards,
Jeff
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100916/6b3161fd/attachment.html>
More information about the core-libs-dev
mailing list