Merge sort и quick sort

Почему O(n²) — это медленно

Пузырёк, выбор и вставки делают порядка n² операций. Для миллиона элементов это триллион действий — минуты работы. Быстрые сортировки работают за O(n log n): тот же миллион — около 20 миллионов операций, доли секунды. Секрет — принцип «разделяй и властвуй»: разбить задачу на половины, решить каждую, объединить.

Сортировка слиянием (merge sort)

Идея в три шага: разделить массив пополам, рекурсивно отсортировать каждую половину, слить две отсортированные половины в одну. Слияние идёт двумя указателями — берём меньший из двух текущих элементов.

Глубина деления — log n уровней (каждый раз пополам), на каждом уровне слияние проходит все n элементов. Итого O(n log n). Merge sort стабилен (не меняет порядок равных) и предсказуем, но требует O(n) дополнительной памяти.

Быстрая сортировка (quick sort)

Quick sort выбирает опорный элемент (pivot) и разбивает массив на «меньше pivot» и «больше pivot», затем рекурсивно сортирует части. В среднем O(n log n) и обычно быстрее merge sort на практике, но в худшем случае (неудачный pivot) — O(n²).

Вернётся [1, 2, 3, 4, 7, 8]. Два указателя сравнивают головы списков и берут меньший; когда один список кончился, дописывается хвост другого. Это сердце merge sort.

⚠️ Частые ошибки новичков

Ошибка. Забыть базовый случай рекурсииПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились. в merge/quick sort. Без if len(arr) <= 1: return arr деление продолжается бесконечно и программа падает с RecursionError. Запустите сломанный код и добавьте базовый случай.