HỌC TIN CÙNG THỦ KHOA

Mời các bạn download tại: Click here

#include <iostream> 
using namespace std;

int n,m,k;
int a[1000], a2[1000];

void Nhap() {
	cout << "Nhap vao so phan tu cua mang a la: ";
	cin >> n;
	cout << "Nhap vao cac phan tu cua mang a: ";
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
}

void Merge(int * x, int * y, int a, int b, int c) {
	// Trong 2 mang x[a..b] va x[b+1..c] thanh mang y[a..c] tang dan
	
	int csbna = a;
	int csbnb = b+1;
	for (int i=a; i<=c; i++){
		if (csbna > b) { // Mang a het phan tu
			for (int k=i; k<=c; k++) {
				y[k] = x[csbnb];
				csbnb++;
			}
			return;
		}
		
		if (csbnb > c){
			for (int k=i;k<=c;k++){
				y[k] = x[csbna];
				csbna++;
			}
			return;
		}
		 
		 
		if (x[csbna] < x[csbnb]) {
			y[i] = x[csbna];
			csbna++;
		}
		else{
			y[i] = x[csbnb];
			csbnb++;
		}
	}
	
}

void MergeByLength(int * x, int * y, int len) {
	int a = 1;
	int b = len;
	int c = 2*len;
	while (c <= n) {
		Merge(x, y, a, b, c);
		a = a + 2*len;
		b = b + 2*len;
		c = c + 2*len;
	}
	
	if (b < n) { // Con 2 mach
				 // - Mach thu nhat co len phan tu tu [a..b]
			 	 // - Mach thu hai co n - b phan tu
		Merge(x, y, a, b, n);	
	}
		else // b >= n, nghia la n <= b: Con 1 mach: [a..n]
			for (int k = a; k<=n; k++) y[k] = x[k];
}


void MergeSort() {
	bool Flag = true;
	int len = 1;
	
	while (len < n) {
		if (Flag == true) MergeByLength(a, a2, len);
			else MergeByLength(a2, a, len);
		len = 2*len;
		Flag = !Flag;
	}
	
	if (Flag == false) {
		for (int i=1; i<=n; i++) a[i] = a2[i];
	}
}

void InKetQua() {
	for(int i=1; i<=n; i++)
		cout << a[i] << " ";
}

int main(){
	
	Nhap();
	MergeSort();
	InKetQua();
	return 0;
}