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
|
#include <iostream>
using namespace std;
int a[] = {11, 2, 9, 7, 8, 3, 2};
int n = 7;
void merge(int *a,int p,int *b,int q, int *c,int n);
void sortMerge(int n, int *a) {
if (n>1) {
int *b = new int[n/2];
int *c = new int[(n + 1)/2];
int i;
for(i=0; i < n/2; i++) {
b[i] = a[i];
}
for(i=n/2; i < n; i++) {
c[i - n/2] = a[i];
}
// Arrays einzeln rekursiv sortieren
sortMerge(n/2, b);
sortMerge(n-n/2, c);
// Arrays b und c zusammenfügen
merge(b,n/2,c,n-n/2,a,n);
// Arrays b und c wieder löschen
delete[] b;
delete[] c;
}
}
void merge(int *b,int p,int *c,int q, int *a,int n) {
int i=0,j=0,k=0;
while(i<p && j<q) {
if(b[i]<=c[j]) {
a[k]=b[i];
i++;
} else {
a[k]=c[j];
j++;
}
k++;
}
if(i==p) {
while(j<q) {
a[k]=c[j];
j++;
k++;
}
} else {
while(i<p) {
a[k]=b[i];
i++;
k++;
}
}
}
int main(){
sortMerge(7, a);
for (int i=0; i<n; i++) cout << a[i] << " ";
return 0;
}
|