/**
 * 歸并排序
 *
 * @author Deters
 * @date 2019/10/12
 */
public class MergeSort {

    /**
     * 歸并
     */
    private static void merge(Integer[] array, int start, int end, int middle) {
        // 臨時(shí)數(shù)組,儲(chǔ)存左右分支合并之后的數(shù)組
        Integer[] temp = new Integer[end - start + 1];
        // 臨時(shí)數(shù)組當(dāng)前位置下標(biāo)
        int index = 0;
        // 左分支下標(biāo)
        int lCt = start;
        // 右分支下標(biāo)
        int rCt = middle + 1;

        // 當(dāng)左右分支都有數(shù)據(jù)時(shí)
        while (lCt <= middle && rCt <= end) {
            temp[index++] = array[lCt] - array[rCt] < 0 ? array[lCt++] : array[rCt++];
        }
        // 只有左分支有數(shù)據(jù)
        while (lCt <= middle) {
            temp[index++] = array[lCt++];
        }
        // 只有右分支有數(shù)據(jù)
        while (rCt <= end) {
            temp[index++] = array[rCt++];
        }

        for (int i = 0; i < temp.length; i++) {
            array[start++] = temp[i];
        }
    }

    /**
     * 分支排序
     */
    private static void mergeSort(Integer[] array, int start, int end) {
        int middle = start + (end - start) / 2;
        if (start < end) {
            // 左分支分割
            mergeSort(array, start, middle);
            // 右分支分割
            mergeSort(array, middle + 1, end);
            // 分支排序并合并
            merge(array, start, end, middle);
            System.out.println(Arrays.toString(array));
        }

    }

    public static void main(String[] args) {
        Random random = new Random();
        Integer[] integers = new Integer[8];
        // 建立數(shù)組
        for (int i = 0; i < 8; i++) {
            integers[i] = random.nextInt(10);
        }

        // 歸并排序
        mergeSort(integers, 0, integers.length - 1);

    }

}