core/org.gnit.lucenekmp.util/IntroSorter

IntroSorter

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 [ ].

Constructors

IntroSorter

constructor()

Types

Companion

object Companion

Functions

binarySort

@JvmOverloads

fun binarySort(from: Int, to: Int, i: Int = from + 1)

A binary sort implementation. This performs O(n*log(n)) comparisons and O(n^2) swaps. It is typically used by more sophisticated implementations as a fall-back when the number of items to sort has become less than {@value #BINARY_SORT_THRESHOLD}. This algorithm is stable.

checkRange

fun checkRange(from: Int, to: Int)

doRotate

open fun doRotate(lo: Int, mid: Int, hi: Int)

heapify

fun heapify(from: Int, to: Int)

heapSort

fun heapSort(from: Int, to: Int)

Use heap sort to sort items between from inclusive and to exclusive. This runs in O(n*log(n)) and is used as a fall-back by IntroSorter. This algorithm is NOT stable.

insertionSort

fun insertionSort(from: Int, to: Int)

Sorts between from (inclusive) and to (exclusive) with insertion sort. Runs in O(n^2). It is typically used by more sophisticated implementations as a fall-back when the number of items to sort becomes less than {@value #INSERTION_SORT_THRESHOLD}. This algorithm is stable.

lower