Sortowanie przez scalanie (ang. merge sort) jest szybkim (niezależnie od danych złożoność O(n lg n)), ekstensywnym (potrzebuje dodatkowej pamięci), lecz stabilnym algorytmem sortowania. Równie dobrze nadaje się do sortowania tablic, jak i list (wersja sortująca listy nie potrzebuje dodatkowej pamięci, listy można scalać w miejscu).

Sortowanie przez scalanie (merge sort) posiada złożoność liniowo-logarytmiczną, jest ekstensywne i stabilne.

Opis algorytmu:

Klasyczna wersja algorytmu jest rekurencyjna: dzielimy wejściową tablicę na dwie równe części, sortujemy przedstawionym algorytmem i scalamy, czyli łączymy dwie posortowane części, w taki sposób, żeby po połączeniu pozostały posortowane.

Zaprezentowana tutaj implementacja jest wersją nierekurencyjną. Dzielimy tablicę na n części jednoelementowych, scalamy ze sobą pary sąsiadujące i otrzymujemy nowy podział, na n/2 części dwuelementowe. Powtarzamy tą czynność (dwuelementowe w 4-elementowe, 4 w 8-elementowe itd.), aż scalimy dwie ostatnie części w całą, posortowaną tablicę. Modyfikacją tego algorytmu jest tzw. sortowanie przez scalanie naturalne, które polega na tym, że w każdym przebiegu pętli wyznaczamy ciągi posortowane w istniejącej tablicy i je scalamy ze sobą. Jest to ogólniejszy przypadek pierwszego wariantu nierekurencyjnego (wszak jeden element jest zawsze posortowany).

Obie wersje - rekurencyjna jak i nierekurencyjna - są ekstensywne, ze względu na to, że do scalania potrzebna jest dodatkowa pamięć, ściślej, potrzebny jest obszar pamięci o rozmiarze tablicy wejściowej. Istnieje wersja in situ, jednak nie posiada ona wielkiej zalety merge sorta - stabilności.

Implementacja (C++):

Procedura scalająca:

/*
src - tablica wejściowa
dst - tablica wyjściowa
l - początek pierwszej ze scalanych części (left)
m - koniec pierwszej części - początek drugiej (middle)
r - koniec drugiej części (right)
*/
void merge(int *src, int* dst, int l, int m, int r){
    int i = l, j = m;
    int d = l;
    while ( d < r ){
	if ( j < r && (i == m || src[i] > src[j]) ){
		dst[d] = src[j++];
	    else
		dst[d] = src[i++];
	}
	++d;
    }
}

Sortowanie (wariant nierekurencyjny, podział 1, 2, 4, 8...):

void sort(int *tab, int n){
    int gap = 1;
    int *tab0 = tab;
    int *tab2 = new int[n];
    for (gap = 1; gap < n; gap *= 2){
	//scalamy 2 części o długości gap
	//w tab - dane wejściowe, tab2 - wyjściowe
	int i;
	for (i = 0; i < n; i += gap * 2){
	    merge(tab, tab2, i, i + gap, min(i + 2 * gap, n));
	}
	int *tmp = tab2; 
	tab2 = tab;
	tab = tmp;
    }
    if (tab != tab0){
	//jeśli skończyliśmy w taki sposób, że dane
	//posortowane wylądowały w tablicy tymczasowej
	//to je przenosimy
	memcpy(tab0, tab, n * sizeof(int));
	delete []tab;
    }else delete []tab2;
}