[Thuật toán] Sắp xếp trộn – Merge Sort

Thuật toán sắp xếp trộn (Merge Sort) là một trong các thuật toán sắp xếp hay được sử dụng. Gần giống với thuật toán sắp xếp nhanh (Quick Sort) về việc sắp xếp bằng việc tách mảng ban đầu thành 2 nửa, nhưng với Quick Sort thì dùng phần tử giữa làm mốc so sánh còn Merge Sort thì chia hẳn ra, sắp xếp từng mảng rồi mới “trộn” 2 mảng đã sắp xếp lại.

Dưới đây là code ngôn ngữ C của thuật toán:

#include <stdio.h>

/* xuat mang a tu vi tri l (left) den vi tri r (right)*/
void xuat(int a[], int l, int r) {
	int i;
	for (i = l; i <= r; i++){
		printf("%d 	", a[i]);
	}
	printf("
");
}

/* tron 2 mang
 * mang a[l -> m] da sap xep
 * mang a[m+1 -> r] da sap xep
 * */
void tron(int a[], int l, int m, int r){
	int i, length;
	int l_end = m - 1;
	i = l;
	length = r - l;
	
	int temp[length];
	
	/* tron cac phan tu cua 2 mang con cua a*/
	while(l <= l_end && m <= r) {
		if (a[l] <= a[m]) {
			temp[i++] = a[l++];
		} else {
			temp[i++] = a[m++];
		}
	}
	
	/* Neu mang dau tien chua het */
	while(l <= l_end) {
		temp[i++] = a[l++];
	}
	
	/* Neu mang thu 2 chua het*/
	while(m <= r) {
		temp[i++] = a[m++];
	}
	
	for (i = 0; i <= length; i++, r--) {
		a[r] = temp[r];
	}
}

/* thuat toan sap xep tron*/
void sx_tron(int a[], int l, int r) {
	//xuat(a, l, r);
	int m;
	if(l < r) {
		m = (l + r) / 2;
		sx_tron(a, l, m);
		sx_tron(a, m + 1, r);
		tron(a, l, m + 1, r);
	}
}

int main(){
	int n = 5;
	int a[] = {2, 6, 3, 8, 5};
	sx_tron(a, 0, n-1);
	
	xuat(a, 0, n - 1);
	return 0;
}