frame|right|Sortowanie przez scalanie w wersji rekurencyjnej Sortowanie przez scalanie () – algorytm sortowania danych, stosujący metodę dziel i zwyciężaj. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi. Algorytm można przedstawić w naiwnej wersji rekurencyjnej lub znacznie bardziej efektywnej wersji iteracyjnej.
Wersja nierekurencyjna Algorytm iteracyjny jest bardzo prosty. W pierwszej iteracji scalamy pojedyncze elementy ciągu w posortowane pary, w drugiej posortowane pary scalamy w posortowane czwórki, następnie czwórki scalamy w posortowane ósemki, i tak dalej, aż w ostatnim przebiegu scalimy dwie posortowane połówki ciągu w posortowaną całość.
Dla ciągu o długości każdy przebieg scalający wymaga operacji, a liczba przebiegów to gdyż pierwszy przebieg tworzy posortowane pary, a każdy następny podwaja długość posortowanych podciągów.
W pseudokodzie algorytm można zapisać następująco: SCALAJ_SORT(T) n ← długość T rozmiar ← 1 DOPÓKI rozmiar < n : DLA i ← 0 DO n - 1 KROK 2 * rozmiar : lewy_pocz ← i lewy_koniec ← min(i + rozmiar - 1, n - 1) prawy_pocz ← lewy_koniec + 1 prawy_koniec ← min(i + 2 * rozmiar - 1, n - 1) JEŚLI prawy_pocz < n : SCALAJ(T, lewy_pocz, lewy_koniec, prawy_koniec) rozmiar ← 2 * rozmiar