Hey Vladimir,
Vladimir Yaroslavskiy writes:
> You are right, the arrays were different: int array was 2'000'000
> and Integer array was 200'000 (and test was run 50 times) - if I
> remember correctly.
Great, that makes sense.
> Now I've run test on the same length 2'000'000 arrays 50 times,
>
Date: Thu, 17 Sep 2009 12:00:57 + (UTC)
From: Ismael Juma
Subject: Re: Replacement of Quicksort in java.util.Arrays with Dual-Pivot
To: core-libs-dev@openjdk.java.net
Hi Vladimir,
Vladimir Yaroslavskiy writes:
random 01 random 01
dpq: 1431 dpq: 8017
tim: 11495
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
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.
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 i
Remarkable performance improvements!
The next step to make this "jdk" material is to implement the DPQ using
collections and generics. Then offer an API to pass a comparator class or insure
the sortable data structure implements comparable interface.
Hi Team,
Thank you very much for your feedback and comments!
I collect here all hints and tips for improvement of
the new algorithm. New version of Quicksort is attached.
And now my investigations:
1. [Jon Bentley]
> Use the median of 2k+1 elements for pivots.
> We can choose a sample of five el