utils/dev.kindling.utils.method.sort/IntroSort

IntroSort

Intro Sort.

A hybrid sorting algorithm that combines QuickSort, HeapSort, and InsertionSort to achieve O(n log n) worst-case performance while keeping Quick Sort's average-case speed in practice.

Strategy:

Delegates partitioning to QuickSort.partition (median-of-three pivot).
Falls back to HeapSort when the recursion depth exceeds 2 * log₂(n), guaranteeing O(n log n) worst case regardless of input shape.
Delegates to InsertionSort.sortRange for partitions of 16 elements or fewer, where insertion sort's low overhead beats recursive algorithms.

Time complexity : O(n log n) in all cases Space complexity: O(log n) stack space

Functions

sort

fun <T : Comparable<T>> sort(array: Array<T>)

Sorts the array in ascending natural order.

fun sort(array: IntArray)

Sorts an IntArray in ascending order.

fun <T> sort(array: Array<T>, comparator: Comparator<T>)

Sorts the array using the given comparator.