Сортировка слиянием
Делит список пополам, сортирует каждую половину и сливает их в один отсортированный список.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- да
- нет
Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
Без дополнительной памяти: сортирует внутри самого списка, без второго списка.
- сравнение
- перемещение
- на окончательном месте
Попробуйте: Выберите «Мало разных значений». Из двух равных значений первым берём то, что из левой половины, поэтому равные значения сохраняют порядок.
Как это работает
Делим список, пока в каждой части не останется по одному значению. Такая часть уже отсортирована. Затем сливаем части попарно: сравниваем первые значения обеих частей и берём меньшее, и так раз за разом. Поднятый ряд в анимации - это дополнительное место, нужное при слиянии.
Когда стоит применять
Когда скорость не должна падать даже в худшем случае, а равные значения должны сохранить свой порядок. Python и Java используют вариант сортировки слиянием. Минус у неё один: нужна дополнительная память.