Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

Vladimir Yaroslavskiy Vladimir.Yaroslavskiy at Sun.COM
Tue Sep 15 10:07:31 UTC 2009

Hello Andrew,

It means that the threshold = 7 is optimal for combination:
insertion sort + Bentley's implementation, and
17 - for Insertion + Dual-Pivot Quicksort.

I can add that for Dual-Pivot Quicksort old threshold = 7
shows slower results than 17.

Other values, such as 25, 27, show similar times as 17,
and I choose last one.

Sorting arrays of tiny size (<= 6) is the sorting by
insertion algorithm and the times are the same in both

Sorting arrays of small size (7 <= & <= 16) is faster by
my implementation (~5-10%)

Thank you,

Andrew Haley wrote:
> One thing that occurred to me, and I'm sorry if this question has been
> asked already but I couldn't find it:
> TINY_SIZE, the threshold for insertion sorting, has gone up from 7 to 17.
> Does this mean that sorting arrays of this size is now slower?
> Andrew.

More information about the core-libs-dev mailing list