initialize

1 files changed, 57 insertions, 0 deletions

diff --git a/c/dataStructure/sorting/mergeSort.c b/c/dataStructure/sorting/mergeSort.c
new file mode 100755
index 0000000..826df71
--- /dev/null
+++ b/c/dataStructure/sorting/mergeSort.c
@@ -0,0 +1,57 @@
+#include<stdio.h>
+
+#define N 10
+
+void merge(int * A, int low, int mid, int high)
+{
+    int m, n;
+    m = mid - low + 1;
+    n = high - mid;
+    int a1[m],a2[n];
+
+    for (int i = 0; i < m; i++)
+        a1[i] = A[low + i];
+    for (int j = 0; j < n; j++)
+        a2[j] = A[mid + 1 + j];
+
+    //compare two subsets, put lower one in sorted array
+    int i = 0, j = 0, k = low;
+
+    while (i < m && j < n)
+    {
+        if (a1[i] <= a2[j])
+            A[k++] = a1[i++];
+        else
+            A[k++] = a2[j++];
+    }
+
+    //Insert remains
+    while (i < m)
+        A[k++] = a1[i++];
+    while (j < n)
+        A[k++] = a2[j++];
+}
+
+void mergeSort(int * A, int low, int high)
+{
+    if (low < high)
+    {
+        int mid = low + (high - low) / 2;
+        mergeSort(A,low,mid);
+        mergeSort(A,mid+1,high);
+        merge(A,low,mid,high);
+    }
+}
+
+int main(void)
+{
+    int A[N] = {12,63,58,95,41,35,65,0,38,44};
+
+    mergeSort(A,0,N - 1);
+
+    for (int i = 0; i < N; i++)
+        printf("%3d",A[i]);
+
+    putchar('\n');
+    return 0;
+}