import java.util.Arrays;

/**
 * Description: 归并排序
 *
 * 采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 将已有序的子序列合并，得到完全有序的序列；
 * 即先使每个子序列有序，再使子序列段间有序。
 * 若将两个有序表合并成一个有序表，称为2路归并
 *
 * 时间复杂度:O(nlogn)
 * Date: 2020-12-26
 * Time: 11:53 AM
 */
public class MergeSort {

    public static void mergeSort(int[] arr,int left,int right) {

        if (right <= left) {
            return;
        }
        int mid = (left + right) >> 1;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        //左右指针同时移动，将两边数组按由大到小的顺序进行合并
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        //如果左边的指针没移动到mid处，说明左边数组还有元素没有处理完毕，直接按顺序往后累加即可
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        //如果右边的指针没移动到mid处，说明右边数组还有元素没有处理完毕，直接按顺序往后累加即可
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
//        System.arraycopy(temp,0,arr,left,temp.length);
    }

    public static void main(String[] args) {

        int[] arr = new int[]{1, 4, 3, 7, 2, 10, 5, 21, 6};
        MergeSort.mergeSort(arr,0,8);
        System.out.println(Arrays.toString(arr));

    }
}