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

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

Пример худшего случая:

const arr = [1, 2, 3, 4, 5]; // Уже отсортированный массив
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0]; // Выбираем первый элемент (худший выбор)
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

Чтобы избежать худшего случая, используют рандомизированный выбор pivot или медиану трёх элементов. В среднем QuickSort работает за O(n log n).