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
119
120
121
|
#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;
}
|
