归并排序

逻辑图

</br>

代码

public static void main(String[] args) {
        int[] array = new int[]{2, 4, 1, 6, 8, 5, 3, 7};
        new Subtyping().mergeSort(array);
        for (int i:
             array) {
            System.out.println(i);
        }
    }


    public void merge(int[] orign, int[] left, int[] right) {
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                orign[k++] = left[i++];
            } else {
                orign[k++] = right[j++];
            }
        }
        while (i < left.length) {
            orign[k++] = left[i++];
        }
        while (j < right.length) {
            orign[k++] = right[j++];
        }
    }

    public void mergeSort(int[] orign) {
        int length = orign.length;
        if (length < 2) {
            return;
        }
        int mid = length / 2;
        int[] left = new int[mid];
        int[] right = new int[length - mid];
        System.arraycopy(orign, 0, left, 0, mid);
        System.arraycopy(orign, mid, right, 0, right.length);

        mergeSort(left);
        mergeSort(right);
        merge(orign, left, right);

    }