core/org.gnit.lucenekmp.util/TimSorter

TimSorter

abstract class TimSorter : Sorter

Sorter implementation based on the TimSort algorithm. It sorts small arrays with a binary sort.

This algorithm is stable. It's especially good at sorting partially-sorted arrays.

NOTE:There are a few differences with the original implementation:

The extra amount of memory to perform merges is configurable. This allows small merges to be very fast while large merges will be performed in-place (slightly slower). You can make sure that the fast merge routine will always be used by having maxTempSlots equal to half of the length of the slice of data to sort.
Only the fast merge routine can gallop (the one that doesn't run in-place) and it only gallops on the longest slice.

Types

Companion

object Companion

Properties

maxTempSlots

val maxTempSlots: Int

minRun

var minRun: Int

runEnds

var runEnds: IntArray

stackSize

var stackSize: Int

var to: Int

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 override fun doRotate(lo: Int, mid: Int, hi: Int)

ensureInvariants

fun ensureInvariants()

exhaustStack

fun exhaustStack()

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