​

基本思想

将数组不断的分成二等份，直至分成每个独立的数，然后将每个二等份合并成每一个有序的整体，在把由他们构成的有序的二等份合并成又一个有序的整体，反反复复，最后得到一个有序的数组。

​​​​​

模板(java)

public static void mergeSort(int[] arr, int left, int right) {
        if(left == right) return;

        int mid = left + right >> 1;

        //分组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        //合并
        int i = left, j = mid + 1, k = 0;
        int[] temp = new int[right - left + 1];
        while(i <= mid && j <= right) {
            if(arr[i] > arr[j]) {
                temp[k ++] = arr[j ++];
            }
            else {
                temp[k ++] = arr[i ++];
            }
        }

        while(i <= mid) {
            temp[k ++] = arr[j ++];
        }

        while(j <= right) {
            temp[k ++] = arr[i ++];
        }

        for(i = left, k = 0; i <= right; i ++, k ++) {
            arr[i] = temp[k];
        }

    }

​