add merge sort

JasonHub5 · JasonHub5 · commit 71bc4b76df74 · 2019-11-08T14:13:24.000+08:00
diff --git a/src/main/java/sort/MergeSort.java b/src/main/java/sort/MergeSort.java
@@ -0,0 +1,35 @@
+package sort;
+
+import java.util.Arrays;
+
+public class MergeSort {
+    public static int[] mergeSort(int[] arr) {
+        if (arr == null || arr.length < 2) {
+            return arr;
+        }
+
+        int mid = arr.length / 2;
+        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
+        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
+
+        return merge(left, right);
+    }
+
+    public static int[] merge(int[] left, int[] right) {
+        int[] result = new int[left.length + right.length];
+
+        int i = 0, j = 0;
+        for (int index = 0; index < result.length; index++) {
+            if (i >= left.length) {
+                result[index] = right[j++];
+            } else if (j >= right.length) {
+                result[index] = left[i++];
+            } else if (left[i] < right[j]) {
+                result[index] = left[i++];
+            } else {
+                result[index] = right[j++];
+            }
+        }
+        return result;
+    }
+}
diff --git a/src/test/java/SortTest.java b/src/test/java/SortTest.java
@@ -1,4 +1,5 @@
 import org.junit.Test;
+import sort.MergeSort;
 import sort.QuickSort;
 
 public class SortTest {
@@ -12,6 +13,16 @@ public void quickSortTest() {
         for (int i : ints) {
             System.out.println(i);
         }
-        System.out.println(arr.toString());
+    }
+
+    @Test
+    public void mergeSortTest() {
+        int[] arr = {10, 23, 2, 4, 5, 7, 24, 1};
+
+        int[] ints = MergeSort.mergeSort(arr);
+
+        for (int i : ints) {
+            System.out.println(i);
+        }
     }
 }
