Вопрос проверяет понимание различий в производительности алгоритмов сортировки quicksort и merge sort в худшем случае.
Quicksort и merge sort — это два популярных алгоритма сортировки, основанных на принципе "разделяй и властвуй". Однако их поведение в худшем случае кардинально отличается из-за разной стратегии разделения данных.
Quicksort выбирает опорный элемент (pivot) и делит массив на две части: элементы меньше pivot и больше pivot. В худшем случае, если pivot каждый раз оказывается минимальным или максимальным элементом (например, при уже отсортированном массиве и выборе первого элемента как pivot), разделение становится крайне неравномерным: одна часть содержит n-1 элемент, а другая — 0. Это приводит к рекурсивной глубине n и общей сложности O(n²).
function quicksort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0]; // плохой выбор для отсортированного массива
const left = arr.slice(1).filter(x => x < pivot);
const right = arr.slice(1).filter(x => x >= pivot);
return [...quicksort(left), pivot, ...quicksort(right)];
}Merge sort делит массив пополам независимо от значений элементов, что гарантирует равномерное разделение. Даже в худшем случае глубина рекурсии составляет log n, а на каждом уровне выполняется слияние за O(n). Таким образом, общая сложность всегда O(n log n).
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}Несмотря на худший случай O(n²), quicksort часто быстрее на реальных данных благодаря меньшим накладным расходам и хорошей локальности кэша. Merge sort требует дополнительной памяти O(n) для слияния, что может быть критично для больших массивов. Выбор между ними зависит от контекста: quicksort предпочтителен для общих задач, а merge sort — когда важна гарантированная производительность.
Вывод: Quicksort эффективнее в среднем, но может деградировать; merge sort стабилен по времени, но требует больше памяти. Используйте quicksort для быстрой сортировки в памяти, а merge sort — для сортировки больших данных или когда важна предсказуемость.
