core/org.gnit.lucenekmp.util/InPlaceMergeSorter

InPlaceMergeSorter

abstract class InPlaceMergeSorter : Sorter

Sorter implementation based on the merge-sort algorithm that merges in place (no extra memory will be allocated). Small arrays are sorted with binary sort.

This algorithm is stable. It's especially suited to sorting small lists where we'd rather optimize for avoiding allocating memory for this task. It performs well on lists that are already sorted.

Inheritors

AutomatonInPlaceMergeSorter

Constructors

InPlaceMergeSorter

constructor()

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