Code:
#include<iostream.h>
#include<conio.h>
#define max 100
void NhapMang(int A[], int n){
for(int i=0;i<n;i++){
cout<<"Phan tu"<<i<<"=";
cin>>A[i];
}
}
void XuatMang(int A[],int n){
cout<<endl;
for(int i=0;i<n;i++)
cout<<A[i]<<"\t";
}
void MergeSort(int m, int n,int &k,int A[],int B[],int C[]){
int i=0,j=0;//[b]O(1)[/b]
k=0;//[b]O(1)[/b]
while (i<m && j<n){
/*[b]O(m).O(n)[/b]*/
if(A[i]<=B[j]){ //[b]O(1)[/b]
C[k]=A[i]; //[b]O(1)[/b]
i++; //O(1)
/*[b]Do phuc tap cua cua cac dong lenh tren la:O(m).O(n)[/b] */
}else{
C[k]=B[j];//[b]O(1)[/b]
j++; //[b]O(1)[/b]
//[b]Do phuc tap cua 2 cau lenh tren la O(1)[/b]
}
k++; //[b]O(1)[/b]
}
if(i<m){ //[b]O(1)[/b]
for(int p=i;p<m;p++){
/*[b]O(m-i)[/b]*/
C[k]=A[p];//[b]O(1)[/b]
k++;//[b]O(1)[/b]
/*[b]Do phuc tap cua ca dong For la O(m-i)[/b] */
}
}else{
for (int p=j;p<n;p++){ //[b]O(n-j)[/b]
C[k]=B[k]; //[b]O(1)[/b]
k++;//[b]O(1)[/b]
/*[b]Do phuc tap cua ca dong For la O(n-j)[/b] */
}
}
}
//[b]Vay do phuc tap cua ham MergeSort la O(m).O(n)[/b]
void main(){
int A[max],B[max],C[max],n,m,k;
clrscr();
cout<<"n=";
cin>>n;
cout<<"m=";
cin>>m;
cout<<"Nhap danh sach co thu tu A:\n";
NhapMang(A,m);
cout<<"\nSAp xep tron 2 mang A,B\n";
MergeSort(m,n,k,A,B,C);
XuatMang(C,k);
getch();
}