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

Быстрая сортировка (QuickSort) имеет следующую сложность:

• Средний и лучший случай: O(n log n). Достигается при хорошем (близком к медиане) выборе опорного элемента (pivot).
• Худший случай: O(n²). Происходит при постоянном выборе наихудшего опорного элемента (например, минимального или максимального), что превращает алгоритм в подобие сортировки выбором.

Оптимизации для избегания худшего случая:

1. Рандомизированный выбор pivot.
2. Выбор медианы трех элементов (первого, среднего, последнего).

Пример реализации на Swift:

func quickSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    // Выбор опорного элемента (здесь — средний)
    let pivot = array[array.count / 2]
    // Разделение на три части
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }
    // Рекурсивная сортировка и объединение
    return quickSort(less) + equal + quickSort(greater)
}

let sorted = quickSort([3, 1, 4, 1, 5, 9, 2, 6])
print(sorted) // [1, 1, 2, 3, 4, 5, 6, 9]

Примечание: Данная реализация для наглядности, но не оптимальна по памяти из-за создания множества новых массивов.