Сортування злиттям
Ділить список навпіл, сортує кожну половину і зливає їх в один відсортований список.
- найкраща Ω(n log n)
- середня Θ(n log n)
- найгірша O(n log n)
- пам'ять O(n)
- стабільне
- потрібна додаткова пам'ять
Що це означає?
- Найкраща: як росте час із розміром списку n, коли вхідні дані для цього алгоритму найлегші.
- Середня: як зазвичай росте час із n. За n² удвічі більше значень - це приблизно вчетверо довше; n log n росте значно повільніше.
- Найгірша: як росте час на найважчих вхідних даних. Важлива, коли швидкість ніколи не має падати.
- Пам'ять: скільки додаткової пам'яті потрібно, крім списку. 1 - кілька змінних, n - копія списку.
- Стабільне: два рівні значення зберігають свій початковий порядок. Важливо, коли сортуємо записи за одним полем.
- Без додаткової пам'яті: сортує всередині самого списку, без другого списку.
- порівняння
- переміщення
- на остаточному місці
Натисніть «Відтворити»: лінії показують, як росте вартість сортування
Натисніть «Відтворити» або проходьте алгоритм крок за кроком.
Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.
Спробуйте: Оберіть список, де мало різних значень. З двох рівних значень першим беремо те, що з лівої половини, тож рівні значення зберігають порядок.
Як це працює
Ділимо список, доки в кожній частині не залишиться по одному значенню. Така частина вже відсортована. Потім зливаємо частини попарно: порівнюємо перші значення обох частин і беремо менше, і так раз за разом. Піднятий ряд в анімації - це додаткове місце, потрібне під час злиття.
Коли варто використовувати
Коли швидкість не повинна падати навіть у найгіршому випадку, а рівні значення мають зберегти свій порядок. Python і Java використовують різновид сортування злиттям. Мінус у нього один: потрібна додаткова пам'ять.