Thuật toán Merge sort

Thuật toán Merge sort



#pragma warning(disable:4996)
#include< conio.h>
#include< stdio.h>



#define MAX 100

void NhapMang(int[], int);
void XuatMang(int[], int);
void Merge_sort(int[], int, int, int);
void Merge(int [], int , int );

void NhapMang(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("\nNhap vao a[%d] = ", i);
scanf("%d", &a[i]);
}
}

void XuatMang(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%4d", a[i]);
}
}


void Merge_sort(int a[], int left, int mid, int right){
int i = left, j = mid + 1, k = 0, n = right - left + 1;
int *B = new int[n];
while ((i < mid + 1) && (j < right + 1)){
if (a[i] < a[j]){
B[k] = a[i];

k++; i++;
}
else {
B[k] = a[j];
k++;
j++;
}
}
while (i < mid + 1){
B[k] = a[i];
i++; k++;
}
while (j < right + 1){
B[k] = a[j];
k++; j++;
}
i = left;
for (int k = 0; k < n; k++){
a[i] = B[k];
i++;
}
delete[] B;

}

void Merge(int a[], int left, int right){
if (left < right){
int mid = (left + right) / 2;
Merge(a,left, mid);
Merge(a, mid + 1, right);
Merge_sort(a, left, mid, right);
}
}

int main(){
int a[MAX], n;


do{
printf("\nNhap vao so luong phan tu cua mang: ");
scanf("%d", &n);

if (n < 0 || n > MAX)
{
printf("\nSo luong phan tu khong hop le. Xin kiem tra lai !");
}
} while (n < 0 || n > MAX);

NhapMang(a, n);
XuatMang(a, n);
Merge(a, 0, n-1);
printf("\n Mang sau khi xep la \n");
XuatMang(a, n);
getch();
return 0;
}