#include "../lib/prng.h" #include "../lib/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; for (int 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; for(int i = 0; i < n; i++) to[i] = from[i]; } void BottomUpMergeSort(uint64_t *A, uint64_t *B) { const int n = SIZE; for (int width = 1; width < n; width = 2 * width) { for (int 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){ if (SIZE <= 0) return -1; uint64_t B[SIZE]; uint64_t *A = res; for (int 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]; srand(42); for (int 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 (int 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__