MergeSort

Z RNO-Wiki

Sortowanie przez scalanie (ang. merge sort).

int T[1000000];   // tablica do posortowania
int tmp[1000000]; // pomocnicza tablica do scalania
int n; // liczba elementów do posortowania
 
void merge_sort(int a, int b) // sortuje tablicę T[a], T[a+1], ..., T[b]
{
	if (a==b) return; // jednej liczby nie musimy sortować
	int m = (a+b)/2;  // środek
	merge_sort(a,m);  // sortujemy lewą połowę tablicy
	merge_sort(m+1,b);// sortujemy prawą połowę tablicy
 
	// scalamy
	static int tmp[1000000]; // tymczasowa tablica
	// typ static oznacza, że jest ona jakby globalna
	// ale widoczna tylko w tej funkcji
	int i=a, j=m+1, k=a;
	while(i<=m && j<=b)
		if (T[i]<T[j]) tmp[k++] = T[i++];
		else           tmp[k++] = T[j++];
	while(i<=m) tmp[k++] = T[i++];
	while(j<=b) tmp[k++] = T[j++];
 
	for (k=a; k<=b; k++) T[k] = tmp[k];
}

Powyższą funkcję stosujemy w następujący sposób:

merge_sort(0, n-1); // sortuj od indeksu 0 do n-1

Rafał Nowak 18:46, 2 sty 2008 (CET)

Osobiste