Thuật toán:
Bước 1 :khởi tạo ba chỉ số chạy trong vòng lặp i = 0, j = 0, k = 0 tương ứng cho ba mảng A, B và C.
Bước 2: tại mỗi bước nếu cả hai chỉ số (i<m và j<n ) ta chọn min(A[i],B[j]) và lưu nó vào trong C[k]. Chuyển sang Bước 4.
Bước 3: tăng giá trị k lên 1 và quay về Bước 2.
Bước 4: sao chép tất cả các giá trị còn lại từ các danh sách mà chỉ số còn vi phạm (tức i<m hoặc j<m) vào trong mảng C.
Cài đặt thuật toán:
#include<math.h>
#include<iostream>
#include<conio.h>
#define max 100
using namespace std;
//Nhập mảng
void NhapMang(int A[],int n){
for(int i=0; i<n; i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
//Xuất mảng
void XuatMang(int A[],int n){
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
//Hoán vị 2 phần tử
void Swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
int i = 0, j = 0;
k = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
}else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m){
for (int p = i; p < m; p++){
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
//Chương trình chính
int main(){
int A[max],B[max],C[max],n,m,k;
cout<<"m = "; cin>>m;
cout<<"n = "; cin>>n;
cout<<"Nhap danh sach co thu tu A:\n";
NhapMang(A,m);
cout<<"Nhap danh sach co thu tu B:\n";
NhapMang(B,n);
cout<<"\nSap xep tron 2 mang A, B\n";
MergeSort(m,n,k,A,B,C);
XuatMang(C,k);
getch();
return 0;
}
Kết quả chạy chương trình:
