/**
 * 归并排序：使用递归，二分拆分，所有拆分的排好序，最后数组也就排好序了NlogN
 * 具体操作：将数组递归拆分成两份，将两边排好序的数组进行比较，由小到大放入临时数组
 */
public class MergeTest {
    public static void main(String[] args) {
        int[] arr = {3,1,6,3,8,3,5,9,4,67,2,5,7,2,6,3,5};
        mergeSort(arr);
        for (int i : arr) {
            System.out.print(i+",");
        }
    }

    private static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int m = l + ((r - l) >> 1);
        // 1、左边部分排序
        process(arr, l, m);
        // 2、右边部分排序
        process(arr, m + 1, r);
        // 3、合并左右两边排好序的数组
        merge(arr, l, m, r);
    }

    private static void merge(int[] arr, int l, int m, int r) {
        // 创建一个临时数组，用来存储当前范围的数组，并进行排序，然后写入原数组
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        // 1、2个数组均排好序了
        // 2、两边从最开始进行比较，小的入临时数组
        // 3、当其中一个数组遍历完，另一个数组剩下的数均是排好序且更大的数字，直接按顺序放入数组即可
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        System.arraycopy(help, 0, arr, l, help.length);
    }
}