File EngineeredQuickSorts.h

↰ Parent directory (ADS/sort)

The quicksorts engineered for speed, beyond the book [see File QuickSort.h for the one of the book and its improvements of section 12.2]:

Definition (ADS/sort/EngineeredQuickSorts.h)

Detailed Description

  • introSort() of Musser: the quicksort with the median of three, whose depth of recursion is bounded by :math:` 2 lfloor log_2 n rfloor , past which the part is sorted by heapsort, so that the worst case is :math: O( n log n ) `; the small parts are sorted by insertion (the std::sort of the C++ libraries);

  • pdqSort(), the pattern-defeating quicksort of Peters: the introsort with the pivot by the median of three, or by the ninther of Tukey on large parts, and three defences against the patterns: a partition that moved nothing is checked by an insertion sort that gives up after 8 moves, so that a sorted or reversed run takes O( n ); a pivot equal to the item before the part, i.e., a run of equal keys, gets a partition that puts the equals on its left and skips them, so that k distinct keys take :math:` O( n log k ) `; a partition too unbalanced (one side below n / 8) swaps a few items to break the pattern, and too many of them fall back to heapsort. On the arithmetic types with their natural order the partition goes by blocks, as in the BlockQuicksort of Edelkamp and Weiss: the items to swap are first collected, 64 at a time, as offsets by an increment with no branch, and then moved along a cycle, so that no comparison causes a mispredicted branch;

  • dualPivotQuickSort() of Yaroslavskiy (the sort of the primitive types of Java 7): two pivots p <= q, the 2nd and the 4th of five equally spaced items, split the part into three, smaller than p, between and larger than q, in one pass; it makes 5 % fewer comparisons and 20 % more swaps than the classical one on average, as Wild and Nebel computed, and fewer scans of the memory, which is what makes it faster;

  • threeWayQuickSort() with the partition of Bentley and McIlroy: the keys equal to the pivot are kept at the two ends during the partition and swapped to the middle at its end, so that they are never sorted again, with the ninther on large parts.

All sort in place and are not stable; the recursion goes into the smaller part and loops on the larger, so that the stack stays :math:` O( log n ) . The contracts [see :ref:`file_ADS_Contract.h]: each sort ends with the same items sorted, an audit. The functions are defined in EngineeredQuickSorts.tpp.

    1. Musser, Introspective sorting and selection algorithms, Software: Practice and Experience 27(8), 983-993, 1997

      1. Peters, Pattern-defeating quicksort, arXiv:2106.05123, 2021

    1. Tukey, The ninther, a technique for low-effort robust (resistant) location in large samples, in H. A. David (ed.), Contributions to Survey Sampling and Applied Statistics, Academic Press, 251-257, 1978

  1. Edelkamp, A. Weiss, BlockQuicksort: how branch mispredictions don’t affect quicksort, Proceedings of ESA 2016, LIPIcs 57, article 38, 2016

  1. Edelkamp, A. Weiss, BlockQuicksort: avoiding branch mispredictions in quicksort, ACM Journal of Experimental Algorithmics 24, article 1.4, 2019, doi:10.1145/3274660

  1. Yaroslavskiy, Dual-pivot quicksort, 2009

  1. Wild, M. E. Nebel, Average case analysis of Java 7’s dual pivot quicksort, Proceedings of ESA 2012, LNCS 7501, 825-836, 2012

    1. Bentley, M. D. McIlroy, Engineering a sort function, Software: Practice and Experience 23(11), 1249-1265, 1993

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions