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. 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
      • setPivot

        protected abstract void setPivot​(int i)
        Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
      • comparePivot

        protected abstract int comparePivot​(int j)
        Compare the pivot with the slot at j, similarly to compare(i, j).