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
|
#include<iostream>
using namespace std;
void merge(int A[], int l, int q, int r) {
int i = l;
int j = q+1;
int k = l;
int B[r];
while((i <= q) && (j <= r)) {
if(A[i] <= A[j])
B[k] = A[i++];
else
B[k] = A[j++];
k++;
}
while(i <= q)
B[k++] = A[i++];
while(j <= r)
B[k++] = A[j++];
for(k = l; k <= r; ++k)
A[k] = B[k];
}
void mergesort(int A[], int l, int r) {
if(l < r) {
int q = (l+r)/2;
mergesort(A, l, q);
mergesort(A, q+1, r);
merge(A, l, q, r);
}
}
int main() {
int a[] = {7,1,22,3,2,12,27,31,6};
for(int i = 0; i < 9; ++i) {
cout << a[i] << ' ';
}
cout << endl;
mergesort(a, 0, 8);
for(int i = 0; i < 9; ++i) {
cout << a[i] << ' ';
}
return 0;
}
|
