#include<iostream>#include<vector>#include<algorithm>#include<string>using namespace std;void Merge(int A[], int p, int q, int r){ int n1=q-p+1; int n2=r-q; int *L=new int[n1+1]; int *R=new int[n2+1]; for(int i=0;i<n1;i++) L[i]=A[p+i-1]; for(int j=0;j<n2;j++) R[j]=A[q+j]; L[n1]=100000; R[n2]=100000; int i=0; int j=0; for(int k=p-1;k<r;k++) { if(L[i]<=R[j]) { A[k]=L[i]; i=i+1; } else { A[k]=R[j]; j=j+1; } }}void MergeSort(int A[], int p, int r){ int q=(p+r)/2; // getchar(); MergeSort(A,p,q); MergeSort(A,p+1,r); Merge(A,p,q,r); }int main(){ /*const int n=8; int A[n]={5,3,6,9,8,7,1,4}; MergeSort(A,0,7);*/ const int n=4; int A[n]={5,3,6,9}; MergeSort(A,0,3); for(int i=0;i<n;i++) cout<<A[i]<<"\t"; getchar(); getchar(); getchar(); return 0;}