Где применяется
1. Задача
Сортировки, которые ты писал раньше, проходят по списку снова и снова. На списке из n элементов они делают примерно n на n сравнений. Для 100 элементов это 10 000 сравнений, и это терпимо. Для миллиона это уже триллион. Нужна сортировка, у которой работа растёт гораздо медленнее.
Начнём с простого факта. Два уже отсортированных списка легко объединить в один отсортированный. Смотришь на первые числа обоих списков и берёшь меньшее, и так снова и снова. Значит, если бы у тебя уже были две отсортированные половины, работа была бы почти сделана.
Сортировка слиянием превращает этот факт в полный метод. Раздели список пополам, отсортируй каждую половину, потом слей две отсортированные половины в одну.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmergeSort([5, 2, 4, 6, 1, 3])Сортируем [5, 2, 4, 6, 1, 3]. Merge sort режет посередине, не глядя на значения, сортирует каждую половину и сливает их.
Одна операция: одно сравнение или одно перемещение. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n²)O(n log n)O(n log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- сортировка массива реального размера (тысячи+)
- нужна гарантированная или ожидаемая O(n log n)
- сортировка как подготовительный шаг перед другим алгоритмом (два указателя, жадный, сканирующая прямая)
- нужна стабильность (сортировка слиянием) или сортировка на месте (быстрая сортировка)
- просто «отсортируй это» без намёка на малое n или особые ключи
Похоже, но не то
- Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion))
Те ничего не делят и стоят n в квадрате. Именно деление и покупает log n.
- Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))
Подсчёт и разряды обгоняют n log n, читая цифры. Им нужны ключи в узком диапазоне.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Пирамидальная сортировка тоже n log n и без буфера. На практике она медленнее на реальных данных.
- Рекурсия (Recursion)
Рекурсия это механизм, а не сам приём. Главное здесь, где проходит разрез.
n до 1e6 даёт O(n log n). Merge требует O(n) дополнительной памяти, quick требует O(log n).
На LeetCode
Задачи, где нужна сортировка за O(n log n) на любом входе, слияние двух отсортированных списков или подсчёт пар прямо во время слияния. Раздели пополам, отсортируй половины и слей их с начала.
mergeSort из урока проходит, потому что держит O(n log n) на любом входе.
Здесь только слияние, и его пишут с конца, чтобы ничего в nums1 не затереть раньше, чем прочитаешь.
Отсортируй оба массива, пройди их вместе, как при слиянии, и оставь совпавшие значения.
Перед каждым слиянием посчитай для каждого значения слева, сколько значений справа меньше его половины.