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
|
#include<stdio.h>
#define N 10
void merge(int * A, int low, int mid, int high)
{
int m, n;
m = mid - low + 1;
n = high - mid;
int a1[m],a2[n];
for (int i = 0; i < m; i++)
a1[i] = A[low + i];
for (int j = 0; j < n; j++)
a2[j] = A[mid + 1 + j];
//compare two subsets, put lower one in sorted array
int i = 0, j = 0, k = low;
while (i < m && j < n)
{
if (a1[i] <= a2[j])
A[k++] = a1[i++];
else
A[k++] = a2[j++];
}
//Insert remains
while (i < m)
A[k++] = a1[i++];
while (j < n)
A[k++] = a2[j++];
}
void mergeSort(int * A, int low, int high)
{
if (low < high)
{
int mid = low + (high - low) / 2;
mergeSort(A,low,mid);
mergeSort(A,mid+1,high);
merge(A,low,mid,high);
}
}
int main(void)
{
int A[N] = {12,63,58,95,41,35,65,0,38,44};
mergeSort(A,0,N - 1);
for (int i = 0; i < N; i++)
printf("%3d",A[i]);
putchar('\n');
return 0;
}
|
