归并排序

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

#include <stdio.h>
#define MAXN 50100
int num[MAXN];
int temp[MAXN];
int n;

void Merge(int l, int mid, int r)
{
int rlen = 0;
int i = l;
int j = mid+1;
while(i <= mid && j <= r)
{
if(num[i] < num[j])
temp[rlen++] = num[i++];
else
temp[rlen++] = num[j++];
}
while(i <= mid)
temp[rlen++] = num[i++];
while(j <= r)
temp[rlen++] = num[j++];

for(int i = 0; i < rlen; ++i)
num[l+i] = temp[i];

}

void MergeSort(int l, int r)
{
if(l >= r)
return;
int mid = (l+r) >> 1;
MergeSort(l,mid);
MergeSort(mid+1,r);
Merge(l,mid,r);
}

int main()
{
scanf("%d",&n);
for(int i = 0; i < n; ++i)
scanf("%d",&num[i]);
MergeSort(0,n-1);
for(int i = 0; i < n; ++i)
printf("%d\n",num[i]);
return 0;
}