The final version of Dual-Pivot Quicksort: v.17
Vladimir Yaroslavskiy
vlv.spb.ru at mail.ru
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.
@Doug,
@Laurent
Could you please look at new sources?
Thank you,
Vladimir
More information about the core-libs-dev
mailing list