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