add merge sort

realDuYuanChao · realDuYuanChao · commit b6314a4e2a95 · 2020-10-02T20:54:33.000+08:00
diff --git a/src/main/java/com/examplehub/sorts/MergeSort.java b/src/main/java/com/examplehub/sorts/MergeSort.java
@@ -0,0 +1,102 @@
+package com.examplehub.sorts;
+
+public class MergeSort implements Sort {
+
+    @Override
+    public void sort(int[] numbers) {
+        mergeSort(numbers, 0, numbers.length - 1);
+    }
+
+    @Override
+    public <T extends Comparable<T>> void sort(T[] array) {
+        mergeSort(array, 0, array.length - 1);
+    }
+
+    /**
+     * Merge sort algorithm implements.
+     *
+     * @param numbers the numbers to be sorted.
+     * @param left    the left index of sub array.
+     * @param right   the right index of sub array.
+     */
+    public static void mergeSort(int[] numbers, int left, int right) {
+        if (left < right) {
+            int middle = (left + right) >> 1;
+            mergeSort(numbers, left, middle);
+            mergeSort(numbers, middle + 1, right);
+            merge(numbers, left, middle, right);
+        }
+    }
+
+    /**
+     * Generic MergeSort algorithm implements.
+     *
+     * @param array the array to be sorted.
+     * @param left  the left index of sub array.
+     * @param right the right index of sub array.
+     * @param <T>   the class of the objects in the array.
+     */
+    public static <T extends Comparable<T>> void mergeSort(T[] array, int left, int right) {
+        if (left < right) {
+            int middle = (left + right) >> 1;
+            mergeSort(array, left, middle);
+            mergeSort(array, middle + 1, right);
+            merge(array, left, middle, right);
+        }
+    }
+
+    /**
+     * @param numbers the numbers to be merged.
+     * @param left    the left index of first sub array.
+     * @param middle  the right index of second sub array.
+     * @param right   the right index of second sub array.
+     */
+    public static void merge(int[] numbers, int left, int middle, int right) {
+        int i = left;
+        int j = middle + 1;
+        int k = left;
+        while (i <= middle && j <= right) {
+            if (numbers[i] <= numbers[j]) {
+                numbers[k++] = numbers[i++];
+            } else {
+                numbers[k++] = numbers[j++];
+            }
+        }
+        while (i <= middle) {
+            numbers[k++] = numbers[i++];
+        }
+
+        while (j <= right) {
+            numbers[k++] = numbers[j++];
+        }
+    }
+
+    /**
+     * Generic merge two sub sorted numbers.
+     *
+     * @param array  the array to be sorted.
+     * @param left   the left index of first sub array.
+     * @param middle the right index of second sub array.
+     * @param right  the right index of second sub array.
+     * @param <T>    the class of the objects in the array.
+     */
+    public static <T extends Comparable<T>> void merge(T[] array, int left, int middle, int right) {
+        int i = left;
+        int j = middle + 1;
+        int k = left;
+        while (i <= middle && j <= right) {
+            if (array[i].compareTo(array[j]) <= 0) {
+                array[k++] = array[i++];
+            } else {
+                array[k++] = array[j++];
+            }
+        }
+        while (i <= middle) {
+            array[k++] = array[i++];
+        }
+
+        while (j <= right) {
+            array[k++] = array[j++];
+        }
+    }
+}
diff --git a/src/test/java/com/examplehub/sorts/MergeSortTest.java b/src/test/java/com/examplehub/sorts/MergeSortTest.java
@@ -0,0 +1,34 @@
+package com.examplehub.sorts;
+
+import com.examplehub.utils.RandomUtils;
+import com.examplehub.utils.SortUtils;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class MergeSortTest {
+    private Sort sort;
+
+    @BeforeEach
+    public void before() {
+        sort = new MergeSort();
+    }
+
+    @Test
+    void testSort() {
+        int[] ints = RandomUtils.randomInts(-50, 50, 100);
+        sort.sort(ints);
+        assertTrue(SortUtils.isSorted(ints));
+    }
+
+    @Test
+    void sortInteger() {
+        Integer[] integers = Arrays.stream(RandomUtils.randomInts(-50, 50, 100))
+                .boxed().toArray(Integer[]::new);
+        sort.sort(integers);
+        assertTrue(SortUtils.isSorted(integers));
+    }
+}
