Dual-Pivot Quicksort and Sorting classes: introspective sort
jeffhain at rocketmail.com
Thu Sep 16 13:33:20 UTC 2010
I talked with Vladimir about using introspective sort along with the new
but it's maybe worth to bring this discussions into this list (as Vladimir
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
(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
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
reaches zero, i.e. when quick sort did too many recursions, remaining sorting is
the O(N*log(N))-in-worst-case backup sort, instead of partitioning again with
For some sorting range widths (50 ? 100 ?), it might not be worth to bother with
anti-quadratic considerations: in that cases, non-introspective sort could be
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
this array would be huge (all we ask to this backup sort is to finish the
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
Introspective sort cost:
- have to initialize a counter using a logarithmic or
- 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the core-libs-dev