Class IntroSorter

  • Direct Known Subclasses:
    ArrayIntroSorter, CollectionUtil.ListIntroSorter

    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. Small arrays are sorted with insertion sort.
    • 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
      • quicksort

        void quicksort​(int from,
                       int to,
                       int maxDepth)
      • 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
      • compare

        protected int compare​(int i,
                              int j)
        Description copied from class: Sorter
        Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).
        Specified by:
        compare in class Sorter