1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
#include<iostream>
using namespace std;
void Merge(int* ans,int* a,int* b,int m,int n) {
int i=0,j=0,k=0;
while(i<=m && j<=n) {
if(i==m) {
ans[k] = b[j];
k++;j++;
}
else if(j==n) {
ans[k] = a[i];
k++;i++;
}
else if(a[i] > b[j]) {
ans[k] = b[j];
k++;j++;
}
else {
ans[k] = a[i];
k++;i++;
}
}
}
int* MergeSort(int* a,int n) {
if(n==1) {
return a;
}
else {
int b[n/2-1],c[n-n/2-1],i;
int *d=0,*e=0,*ans=0;
for(i=0;i<n/2;i++) {
b[i] = a[i];
c[i] = a[n/2+i];
}
if(n%2 == 1) {
c[i] = a[n-1];
}
d = MergeSort(b,n/2);
e = MergeSort(c,n-n/2);
Merge(ans,d,e,n/2,n-n/2);
return ans;
}
}
int main() {
int a[] = {9,8,7,6,5,4,3,2,1},i;
int *b=0;
b = MergeSort(a,9);
for(i=0;i<9;i++)
cout<<b[i]<<endl;
}
|