The final version of Dual-Pivot Quicksort: v.17

Vladimir Yaroslavskiy at
Tue Apr 2 20:51:49 UTC 2019

Hi team,

Please find my improved version, v17, it was optimized
for sorting small arrays.

Summary of changes:

1. Mixed insertion sort is introduced: it is combination
of simple insertion sort, pin insertion sort and pair
insertion sort. Simple insertion sort is invoked on
tiny array. In case of small part we start with pin
insertion sort (small element is inserted at the beginning,
large element is moved to the end). Then we continue with
pair insertion sort on remain part. Optimized combination
of various types of insertion sorts allows to increase
threshold for Quicksort and makes whole sorting faster.

2. Heap sort is used only if execution time is becoming
quadratic, not for sorting small arrays.

3. New tests are added against heap sort.

4. Minor javadoc changes: double spaces are removed.

ParallelSorting class will be deleted, because Sorting
test class covers both: sequential and parallel algorithms.

Could you please look at new sources?

Thank you,

More information about the core-libs-dev mailing list