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
|
#include "../prng/prng.h"
#include "../prng/types.h"
//https://en.wikipedia.org/wiki/Merge_sort
#ifdef __UNIT_TEST_MERGE__
#define SIZE 100
#else
#include "test.h"
#endif
int min(int a, int b){
return (a < b)?a:b;
}
void BottomUpMerge(const uint64_t *A, int iLeft, int iRight, int iEnd, uint64_t *B)
{
int i = iLeft, j = iRight, k;
for (k = iLeft; k < iEnd; k++) {
if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i = i + 1;
} else {
B[k] = A[j];
j = j + 1;
}
}
}
void CopyArray(uint64_t *to, const uint64_t *from)
{
const int n = SIZE;
int i;
for(i = 0; i < n; i++)
to[i] = from[i];
}
void BottomUpMergeSort(uint64_t *A, uint64_t *B)
{
const int n = SIZE;
int width, i;
for (width = 1; width < n; width = 2 * width)
{
for (i = 0; i < n; i = i + 2 * width)
{
BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
}
CopyArray(A, B);
}
}
int merge_sort(uint64_t *res, const uint64_t *T){
int i;
if (SIZE <= 0)
return -1;
uint64_t B[SIZE];
uint64_t *A = res;
for (i = 0 ; i < SIZE ; i++)
A[i] = T[i];
BottomUpMergeSort(A, B);
return 0;
}
#ifdef __UNIT_TEST_MERGE__
int main(void){
uint64_t T[SIZE];
uint64_t res[SIZE];
int i;
srand(42);
for (i = 0 ; i < SIZE ; i++)
T[i] = randlong();
/* Sorting the table */
if (merge_sort(res, T) < 0) return -1;
/* Computing max(T) */
uint64_t max = T[0];
for (i = 1 ; i < SIZE ; i++)
if (T[i] > max)
max = T[i];
/* We should have: max(T) == res[SIZE] */
return !(max == res[SIZE-1]);
}
#endif // __UNIT_TEST_MERGE__
|
