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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
/*
* Merge sorting integers from stdin
* Copyright (C) 2019, Nguyễn Gia Phong
* This software is licenced under a CC BY-SA 4.0 license
*/
#include <stdio.h>
#include <stdlib.h>
#include "construct.h"
construct *merge(construct *left, construct *right,
int (*compar)(const void *, const void *))
{
if (left == NULL)
return right;
if (right == NULL)
return left;
if (compar(car(left), car(right)) <= 0)
return cons(car(left), merge(cdr(left), right, compar));
return cons(car(right), merge(left, cdr(right), compar));
}
construct *msort(construct *list, int (*compar)(const void *, const void *))
{
construct *rest, *left = NULL, *right = NULL;
while (list != NULL) {
left = cons(car(list), left);
rest = cdr(list);
if (rest == NULL)
break;
right = cons(car(rest), right);
list = cdr(rest);
}
if (left == NULL)
return right;
if (right == NULL)
return left;
return merge(msort(left, compar), msort(right, compar), compar);
}
int cmp(const void *x, const void *y)
{
return *(int *) x - *(int *) y;
}
construct *iread(size_t n)
{
if (!n)
return NULL;
int *tmp = malloc(sizeof(int));
scanf("%d", tmp);
return cons(tmp, iread(n - 1));
}
void iprint(construct *list)
{
if (list == NULL) {
putchar(10);
} else {
printf("%d ", *(int *) car(list));
iprint(cdr(list));
}
}
int main()
{
size_t n;
scanf("%zu", &n);
iprint(msort(iread(n), cmp));
return 0;
}
|
