Dual-Pivot Quicksort and Sorting classes: introspective sort

[Jeff Hain]

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>