Sortowanie przez scalanie

Dzieli listę na pół, sortuje każdą połowę, a potem scala obie połowy w jedną posortowaną listę.

najlepszy Ω(n log n)
średni Θ(n log n)
najgorszy O(n log n)
pamięć O(n)
stabilny
wymaga dodatkowej pamięci

Co to znaczy?

Najlepszy przypadek: jak czas rośnie z rozmiarem listy n, gdy dane są dla tego algorytmu najłatwiejsze.
Średni: jak czas zwykle rośnie z n. Przy n² dwa razy więcej wartości sortuje się około czterech razy dłużej; n log n rośnie dużo wolniej.
Najgorszy przypadek: jak rośnie czas przy najtrudniejszych danych. Ważny, gdy sortowanie nigdy nie może zwolnić.
Pamięć: ile dodatkowej pamięci potrzeba poza listą. 1 to kilka zmiennych, n to kopia listy.
Stabilny: dwie równe wartości zachowują pierwotną kolejność. Ważne przy sortowaniu rekordów według jednego pola.
Bez dodatkowej pamięci: sortuje w samej liście, bez drugiej listy.

porównywanie
przenoszenie
na właściwym miejscu

0 / 263 kroków

Porównania Zapisy

Naciśnij Odtwórz, a linie pokażą, jak rośnie koszt

Szybkość 8 kroków/s

Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.

Spróbuj: Wybierz listę z małą liczbą różnych wartości. Gdy dwie są równe, najpierw brana jest ta z lewej połowy, więc ich kolejność się nie zmienia.

Jak to działa

Dziel listę na coraz mniejsze kawałki, aż w każdym zostanie jedna wartość. Taki kawałek jest już posortowany. Potem scalaj kawałki parami: porównuj pierwsze wartości obu kawałków i za każdym razem bierz mniejszą. Uniesiony rząd w animacji to dodatkowa pamięć zajęta podczas scalania.

Kiedy warto go użyć

Gdy sortowanie ma być szybkie nawet w najgorszym przypadku, a równe wartości nie mogą zamienić się miejscami. Z odmiany tego algorytmu korzystają Python i Java. Wadą jest to, że potrzebuje dodatkowej pamięci.