Rekurencyjnie dzieli tablicę na połowy i scala posortowane części. Złożoność O(n log n).
Sortowanie przez scalanie to klasyczny algorytm wykorzystujący strategię "dziel i zwyciężaj" (divide and conquer). Składa się z dwóch faz:
Faza dzielenia: tablicę rekurencyjnie dzielimy na dwie połowy, aż otrzymamy fragmenty o długości 1 lub 0 (które są już posortowane).
Faza scalania: dwie posortowane tablice łączymy w jedną posortowaną, porównując elementy z początku obu fragmentów i wybierając mniejszy.
Cecha charakterystyczna: algorytm jest stabilny – zachowuje względną kolejność elementów o równych wartościach.
Łatwy podział, trudne łączenie: to dobry sposób, by porównać sortowanie przez scalanie z sortowaniem szybkim. Tutaj podział jest trywialny – tablicę przecinamy dokładnie na pół, bez ani jednego porównania elementów. Cała właściwa praca (porównania i układanie w kolejności) dzieje się dopiero w fazie scalania. W sortowaniu szybkim jest odwrotnie: tam trudny jest podział wokół elementu osiowego, a łączenie wyników nie wymaga już żadnej pracy.
Ciekawostka: procedura scalania dwóch posortowanych fragmentów jest sercem Timsorta – hybrydowego algorytmu, którego Python używa jako domyślnego sort.
Na maturze: sztandarowy przykład rekurencji i strategii "dziel i zwyciężaj".
Podział – dzielimy na połowy, aż zostaną pojedyncze elementy:
Scalanie – łączymy posortowane fragmenty z powrotem w większe:
Prześledź krok po kroku, jak algorytm porządkuje tablicę. Porównywane elementy są podświetlone, a te, które trafiły na swoje docelowe miejsce, zmieniają kolor na zielony.
Naciśnij „Krok", aby wykonać jedną operację, albo „Auto", aby uruchomić całą animację.
funkcja scal(L, P): wynik ← pusta lista i ← 0 j ← 0 // przechodzimy obie tablice jednocześnie dopóki i < długość(L) oraz j < długość(P): jeżeli L[i] ≤ P[j]: dodaj L[i] do wynik i ← i + 1 w przeciwnym razie: dodaj P[j] do wynik j ← j + 1 // dopisujemy pozostałe elementy dopóki i < długość(L): dodaj L[i] do wynik i ← i + 1 dopóki j < długość(P): dodaj P[j] do wynik j ← j + 1 zwróć wynik funkcja sortuj_przez_scalanie(T): jeżeli długość(T) ≤ 1: zwróć T srodek ← długość(T) div 2 L ← sortuj_przez_scalanie(T[0..srodek - 1]) P ← sortuj_przez_scalanie(T[srodek..koniec]) zwróć scal(L, P)
def scal(lewa, prawa):
wynik = []
i = j = 0
while i < len(lewa) and j < len(prawa):
if lewa[i] <= prawa[j]:
wynik.append(lewa[i])
i += 1
else:
wynik.append(prawa[j])
j += 1
# dopisujemy pozostałe elementy z dłuższej tablicy
wynik.extend(lewa[i:])
wynik.extend(prawa[j:])
return wynik
def sortowanie_przez_scalanie(tablica):
if len(tablica) <= 1:
return tablica
srodek = len(tablica) // 2
lewa = sortowanie_przez_scalanie(tablica[:srodek])
prawa = sortowanie_przez_scalanie(tablica[srodek:])
return scal(lewa, prawa)
# Przykład użycia
dane = [64, 25, 12, 22, 11, 90, 3]
print(sortowanie_przez_scalanie(dane))
# Wynik: [3, 11, 12, 22, 25, 64, 90]#include <vector>
#include <iostream>
using namespace std;
// scala dwie posortowane części tablicy t: [lewy..srodek] oraz [srodek+1..prawy]
void scal(vector<int>& t, int lewy, int srodek, int prawy) {
vector<int> pom;
int i = lewy; // wskaźnik lewej części
int j = srodek + 1; // wskaźnik prawej części
// przechodzimy obie części jednocześnie, wybierając mniejszy element
while (i <= srodek && j <= prawy) {
if (t[i] <= t[j]) pom.push_back(t[i++]);
else pom.push_back(t[j++]);
}
// dopisujemy pozostałe elementy
while (i <= srodek) pom.push_back(t[i++]);
while (j <= prawy) pom.push_back(t[j++]);
// przepisujemy scalony wynik z powrotem do tablicy
for (int k = 0; k < (int)pom.size(); k++)
t[lewy + k] = pom[k];
}
// rekurencyjnie dzieli zakres na pół i scala posortowane połowy
void sortowanie_przez_scalanie(vector<int>& t, int lewy, int prawy) {
if (lewy >= prawy) return; // fragment o długości 0 lub 1 jest już posortowany
int srodek = lewy + (prawy - lewy) / 2;
sortowanie_przez_scalanie(t, lewy, srodek);
sortowanie_przez_scalanie(t, srodek + 1, prawy);
scal(t, lewy, srodek, prawy);
}
int main() {
vector<int> dane = {64, 25, 12, 22, 11, 90, 3};
sortowanie_przez_scalanie(dane, 0, dane.size() - 1);
for (int x : dane) cout << x << " ";
// Wynik: 3 11 12 22 25 64 90
}Nie – w fazie scalania powstaje dodatkowa tablica, do której trafiają posortowane elementy z obu fragmentów, a dopiero potem wynik wraca do oryginalnej tablicy. Stąd złożoność pamięciowa O(n) (patrz sekcja „Złożoność").
Rekurencję warto przerywać wcześniej: dla bardzo krótkich fragmentów sortowanie przez wstawianie wykonuje mniej operacji niż dalsze dzielenie i scalanie. To dokładnie ta sama sztuczka, na której opiera się Timsort.
Sortowanie przez scalanie radzi sobie równie dobrze z każdym zestawem danych – dużym, małym, dowolnie rozłożonym. Sortowanie szybkie bywa za to szybsze w praktyce na małych tablicach, głównie dzięki mniejszym stałym i lepszemu wykorzystaniu pamięci podręcznej procesora.
Nie – ma dokładnie taką samą złożoność w najlepszym, średnim i najgorszym przypadku, niezależnie od tego, jak ułożone są dane wejściowe. To odróżnia je od sortowania przez wstawianie, które na prawie posortowanych danych działa niemal liniowo.
Złożoność O(n log n) jest gwarantowana zawsze, ale sama liczba porównań w fazie scalania bywa różna. Jest największa, gdy elementy obu scalanych fragmentów przeplatają się na zmianę w finalnej kolejności (np. scalanie [1, 3] i [2, 4]) – wtedy trzeba porównać niemal każdą parę, zanim wybierze się mniejszy element.
O(n log n)O(n log n)O(n)Czas O(n log n) – zawsze. Dzielenie tworzy log n poziomów rekurencji (za każdym razem połowa), a na każdym poziomie scalanie przegląda wszystkie n elementów. Daje to log n poziomów × O(n) pracy = O(n log n). Co ważne, ten rząd jest gwarantowany niezależnie od danych – nie ma złego przypadku, jak w sortowaniu szybkim.
Pamięć O(n). Przy scalaniu tworzymy tablice pomocnicze na wyniki – to koszt O(n). Rekurencja odkłada dodatkowo po jednej ramce na każdy poziom podziału, czyli O(log n) na stosie. Ponieważ w Big-O liczy się składnik dominujący, a n rośnie szybciej niż log n, całość zapisujemy jako O(n). Ta dodatkowa pamięć to główna wada w porównaniu z algorytmami sortującymi w miejscu.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: