Class IntroSorter


  • public abstract class IntroSorter
    extends Sorter
    Sorter implementation based on a variant of the quicksort algorithm called introsort: when the recursion level exceeds the log of the length of the array to sort, it falls back to heapsort. This prevents quicksort from running into its worst-case quadratic runtime. Selects the pivot using Tukey's ninther median-of-medians, and partitions using Bentley-McIlroy 3-way partitioning. Small ranges are sorted with insertion sort.

    This algorithm is NOT stable. It's fast on most data shapes, especially with low cardinality. If the data to sort is known to be strictly ascending or descending, prefer TimSorter.

    NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.
    • Constructor Detail

      • IntroSorter

        public IntroSorter()
        Create a new IntroSorter.
    • Method Detail

      • sort

        public final void sort​(int from,
                               int to)
        Description copied from class: Sorter
        Sort the slice which starts at from (inclusive) and ends at to (exclusive).
        Specified by:
        sort in class Sorter
      • setPivot

        protected abstract void setPivot​(int i)
        Description copied from class: Sorter
        Save the value at slot i so that it can later be used as a pivot, see Sorter.comparePivot(int).
        Overrides:
        setPivot in class Sorter
      • comparePivot

        protected abstract int comparePivot​(int j)
        Description copied from class: Sorter
        Compare the pivot with the slot at j, similarly to compare(i, j).
        Overrides:
        comparePivot in class Sorter