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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>
#define DO_PRINT 0
void printArr(int *arr, size_t len)
{
printf("{");
for (int i = 0; i < len; i++) {
printf(" %d%s", arr[i], i + 1 == len ? " " : ",");
}
printf("}\n");
}
int *genArr(size_t len, int div)
{
/* Make array */
int *arr = (int *)malloc(len * sizeof(int));
if (arr == NULL) {
return NULL;
}
/* Fill it with random */
while (len--) {
arr[len] = div - (rand() % (div * 2));
}
return arr;
}
int mergeSort(int *arr, size_t len)
{
/* Check if len is one(then it's sorted */
if (len <= 1) {
return 0;
}
/* Calculate array sizes */
size_t q = len / 2;
size_t rl = len - q;
/* Make arrays */
int *left = (int *)malloc(q * sizeof(int));
if (left == NULL) {
return 1;
}
int *right = (int *)malloc(rl * sizeof(int));
if (right == NULL) {
return 1;
}
/* Copy data */
memcpy(left, arr, q * sizeof(int));
memcpy(right, arr + q, rl * sizeof(int));
/* Sort each */
mergeSort(left, q);
mergeSort(right, rl);
/* Merge them into arr */
for (int i = 0, j = 0, k = 0; k < len; k++) {
if (i < q && (j == rl || left[i] <= right[j])) {
arr[k] = left[i++];
} else {
arr[k] = right[j++];
}
}
/* Free the pointers */
free(left);
free(right);
return 0;
}
void test(size_t len)
{
int *a = genArr(len, len);
#if DO_PRINT == 1
printArr(a, len);
printf("\n\n");
#endif
clock_t begin = clock();
mergeSort(a, len);
clock_t end = clock();
#if DO_PRINT == 1
printArr(a, len);
#endif
clock_t diff = end - begin;
printf("Sorting %d long array took %d : %f s\n", len, diff,
(double)diff / CLOCKS_PER_SEC);
free(a);
}
void bench()
{
size_t len = SIZE_MAX;
srand((unsigned)time(NULL));
for (int i = 1; i < len; i *= 2) {
test(i);
}
}
int main(void)
{
bench();
return 0;
}
|
