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

[Vladimir Yaroslavskiy]

Hi,

I've asked about TimSort vs. Dual-Pivot Quicksort.
As Joshua said, these algorithms are for different
purposes: TimSort (and MergeSort) for sorting complex
objects, because it is stable (doesn't change the
order of equal elements), and Quicksort is for
primitive types. And these algorithms shows
the best results in own fields:

      int          java.lang.Integer

      random              random
dpq: 16063          dpq: 10403
tim: 36806          tim: 9281
jdk: 21907          jdk: 9953

   ascendant           ascendant
dpq: 5558           dpq: 498
tim: 322            tim: 203
jdk: 8304           jdk: 797

  descendant          descendant
dpq: 5762           dpq: 6077
tim: 605            tim: 235
jdk: 8383           jdk: 5718

  all equal           all equal
dpq: 255            dpq: 577
tim: 326            tim: 297
jdk: 604            jdk: 1125

organ pipes         organ pipes
dpq: 8999           dpq: 6002
tim: 1758           tim: 1283
jdk: 11636          jdk: 5155

   random 01           random 01
dpq: 1431           dpq: 8017
tim: 11495          tim: 2717
jdk: 1552           jdk: 8547

Thanks,
Vladimir

Date: Mon, 14 Sep 2009 14:30:26 -0700
From: Joshua Bloch <jjb at google.com>
Subject: Re: Replacement of Quicksort in java.util.Arrays with
	Dual-Pivot 	Quicksort: improvements
To: Leonid Geller <lgeller at feedroom.com>
Cc: core-libs-dev at openjdk.java.net

Leonid,
I don't think Dual Pivot Quicksort for List is necessary or appropriate.
  Recall that Arrays.sort and Collections.sort are defined to be stable
sorts, which Quicksort is not.  Also, I just replaced them with TimSort,
which gives a very healthy performance boost.

I do think it would be an interesting experiment to run Dual Pivot Quicksort
on object reference arrays, and TimSort on primitive arrays, but I don't
think we'll end up putting either into the JDK.

            Josh