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 <[email protected]>
Subject: Re: Replacement of Quicksort in java.util.Arrays with
Dual-Pivot Quicksort: improvements
To: Leonid Geller <[email protected]>
Cc: [email protected]
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
