Какая алгоритмическая сложность быстрой сортировки

Быстрая сортировка (QuickSort) имеет среднюю сложность O(n log n). В худшем случае (например, при неудачном выборе опорного элемента) сложность может деградировать до O(n²). Однако на практике QuickSort часто быстрее других алгоритмов сортировки из-за эффективного использования кэша и малых констант.

fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
    if (low < high) {
        val pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low
    for (j in low until high) {
        if (arr[j] < pivot) {
            arr.swap(i, j)
            i++
        }
    }
    arr.swap(i, high)
    return i
}