Sortowanie przez scalanie

Sortowanie przez scalanie zamienia jeden trudny problem w wiele łatwych: dwie posortowane listy łatwo połączyć w jedną. Dziel listę na pół, aż każdy kawałek będzie pojedynczą wartością, a potem scal kawałki z powrotem. To klasyczny algorytm typu „dziel i zwyciężaj”, a jego czas to n log n niezależnie od danych.

Dwie posortowane połowy listy przeniesione do rzędu bufora i mniejsza z pierwszych wartości wracająca w górę do listy
Dwie posortowane połowy listy przeniesione do rzędu bufora i mniejsza z pierwszych wartości wracająca w górę do listy

Idea

Scalanie to łatwa część. Mając dwie listy, z których każda jest posortowana, porównaj ich pierwsze wartości i weź mniejszą. Porównaj nowe pierwsze wartości i znów weź mniejszą. Gdy jedna lista się skończy, dopisz resztę drugiej. Każdy krok zabiera jedną wartość, więc scalenie dwóch list o łącznej długości m wymaga najwyżej m − 1 porównań. Sortowanie przez scalanie wykorzystuje to do sortowania: podziel listę na pół, posortuj każdą połowę sortowaniem przez scalanie i scal obie połowy.

Przykład

Weźmy 5, 1, 4, 2, 8. Dzielimy na 5, 1 oraz 4, 2, 8. Pierwsza połowa dzieli się na 5 i 1, które scalają się w 1, 5. Druga połowa dzieli się na 4 oraz 2, 8; 2, 8 powstaje ze scalenia 2 i 8, a potem jest scalane z 4 w 2, 4, 8. Na koniec scalamy 1, 5 oraz 2, 4, 8: 1, potem 2, potem 4, potem 5, a 8 zostaje. To 8 porównań, 12 zapisów i 4 scalenia.

Dlaczego n log n

Każdy podział połowi kawałki, więc po około log₂ n poziomach każdy kawałek jest pojedynczą wartością. W drodze powrotnej każdy poziom scaleń obsługuje każdą wartość raz, czyli n zapisów i mniej niż n porównań na poziom. Łącznie daje to około n log₂ n. Dla 40 wartości sortowanie wykonuje 216 zapisów i najwyżej 177 porównań; sortowanie bąbelkowe może dla tej samej listy potrzebować 780 porównań. Kolejność danych ma znacznie mniejsze znaczenie niż w tamtych algorytmach: dla 40 wartości lista posortowana wymaga 100 porównań, odwrócona 116, a losowa około 160.

Bufor i stabilność

Aby scalić dwie połowy leżące obok siebie w liście, zwykła metoda kopiuje je do bufora i zapisuje z powrotem w kolejności. Aplikacja pokazuje ten bufor jako drugi rząd słupków. Wymaga on tyle dodatkowej pamięci, ile zajmuje lista, i to główny koszt sortowania przez scalanie. W zamian sortowanie jest stabilne: gdy dwie pierwsze wartości są równe, najpierw idzie ta z lewej połowy, więc równe wartości zachowują kolejność. Stabilność ma znaczenie, gdy sortuje się rekordy po kolejnych polach.

Historia i zastosowania

John von Neumann opisał sortowanie przez scalanie w 1945 roku, co czyni je jednym z pierwszych algorytmów napisanych dla komputera z programem w pamięci. Ponieważ czyta i zapisuje dane długimi seriami, było standardową metodą sortowania danych na taśmach i nadal służy do sortowania plików zbyt dużych, by zmieściły się w pamięci. Timsort, używany w języku Python oraz w języku Java dla obiektów, to sortowanie przez scalanie, które najpierw wyszukuje już posortowane serie, a krótkie kawałki sortuje przez wstawianie.

John von Neumann na zdjęciu z identyfikatora z Los Alamos. W 1945 opisał sortowanie przez scalanie, jeden z pierwszych algorytmów napisanych dla komputera z zapisanym programem.
John von Neumann na zdjęciu z identyfikatora z Los Alamos. W 1945 opisał sortowanie przez scalanie, jeden z pierwszych algorytmów napisanych dla komputera z zapisanym programem.

Wypróbuj

Otwórz aplikację i naciśnij Krok. Zacieniona część listy jest właśnie dzielona lub scalana, a przerywana linia oznacza środek. Gdy zaczyna się scalanie, obie połowy opadają do rzędu bufora; dwie pierwsze wartości są porównywane, a mniejsza wraca w górę. Obserwuj liczniki: zapisów jest tyle samo dla każdej listy tej samej długości, a porównań jest najmniej dla listy posortowanej lub odwróconej i najwięcej dla losowej, ale nigdy więcej niż około n log₂ n.

Często zadawane pytania

Jaka jest złożoność czasowa sortowania przez scalanie?

O(n log n) w przypadku optymistycznym, średnim i pesymistycznym. Zwykła wersja potrzebuje O(n) dodatkowej pamięci na bufor.

Czym różni się sortowanie przez scalanie od sortowania szybkiego (quicksort)?

Oba dzielą listę i sortują części. Sortowanie przez scalanie dzieli w środku, nie patrząc na wartości, a pracę wykonuje przy scalaniu; quicksort pracuje przy dzieleniu, przesuwając wartości wokół elementu osiowego, i nie potrzebuje scalania. Quicksort sortuje w miejscu i w praktyce często jest szybszy, ale przy złych danych może zwolnić do n² i nie jest stabilny. Sortowanie przez scalanie jest zawsze n log n i stabilne.

Czym jest wstępujące sortowanie przez scalanie (bottom-up)?

To wersja bez rekurencji: najpierw scal sąsiednie pojedyncze wartości w pary, potem pary w czwórki i tak dalej, w każdej rundzie podwajając długość. Wykonuje tę samą pracę co pokazana tu wersja zstępująca (top-down).

Czy sortowanie przez scalanie jest stabilne?

Tak, o ile przy remisie najpierw brana jest wartość z lewej połowy, tak jak w tej aplikacji.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj sortowanie przez scalanie