1 files changed, 92 insertions, 0 deletions
diff --git a/test/kvx/sort/merge.c b/test/kvx/sort/merge.c
new file mode 100644
index 00000000..99f8ba85
--- /dev/null
+++ b/test/kvx/sort/merge.c
@@ -0,0 +1,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__