🍉算法思想

归并排序（Merge sort）是建立在归并的有效操作上进行排序，主要采用分治法将已有序的子序列合并，得到完全有序的序列。即先让每一小段有序，再让小段之间变得有序。

将两个有序段归并为一个有序段，称为二路归并；有序段称为归并段。

分治法：将一个大问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之。

如下图所示：

?

🥝算法描述

①开始以间隔为1进行归并，即第一个元素跟第二个进行归并。第三个与第四个进行归并

②再以间隔为2进行归并，即1-4进行归并，5-8进行归并

③再以2 * 2的间隔进行归并，同理，直到2 * k超过数组的长度为止。

④当不够两组进行归并时，如果超过k个元素元素，仍然进行归并；如果剩余元素不超过k个元素，就直接复制给中间数组。

🍒实例

对 26 53 67 48 57 13 49 32 60 50 按升序顺序进行归并排序。

治阶段的结果如下：

具体步骤：

1、开始时gap=1，进行归并

?2、gap=2时，进行归并（gap以2的倍数依次增长）

?这轮排序需要注意：最后只剩下一个有序段[50,60]，没有与之对应的有序段存在，则不需要归并。

3、gap=4和gap=8如下：

?代码实现：

public class MergeSort {
    private static void marge(int[] arr,int gap){
        int left1 = 0;//第一个序列的左边界
        int right1 = left1 + gap - 1; //第一个序列的右边界
        int left2 = right1 + 1;//第二个序列的左边界
        //第二个序列的右边界分两种情况 ：
        // 1）其序列左边界 + gap - 1如果超过序列长度，则右边界直接等于数组的最大下标
        // 2)其序列左边界 + gap - 1如果没有超过序列长度，则右边界等于 left2 + gap - 1
        int right2 = left2 + gap - 1 > arr.length - 1  ? arr.length - 1 : left2 + gap - 1;

        //开辟一个与数组arr相同长度的brr数组，用来在归并排序过程中存放已经完成排序的序列
        int[] brr=new int[arr.length];
        int j = 0;//控制新数组的下标
        //！！！！有两个归并段
        //合并两个有序序列，谁小谁存放在brr中
        while (left2 < arr.length) {
            while (left1 <= right1 && left2 <= right2) {
                if (arr[left1] < arr[left2]) {
                    brr[j++] = arr[left1++];//放完值之后，下标都自增
                }else {
                    brr[j++] = arr[left2++];
               }
            }

            //如果其中一个序列中的元素全部排序完，将另一个序列剩余元素直接归入brr数组中
            if (left1 > right1) {
                while(left2 <= right2) {
                    brr[j++] = arr[left2++];
                }
            }
            if (left2 > right2) {
                while (left1 <= right1) {
                    brr[j++] = arr[left1++];
                }
            }

            //更新两个待排序序列的左右下标
            left1 = right2 + 1;
            right1 = left1 + gap - 1;
            left2 = right1 + 1;
            right2 = left2 + gap - 1 > arr.length - 1 ? arr.length - 1 : left2 + gap - 1;
        }

        //！！！！剩余一个归并段，而且只能是左归并段
        while(left1 <= arr.length - 1) {
            brr[j++] = arr[left1++];
        }

        System.arraycopy(brr,0,arr,0,arr.length);//将brr中的排完序的数据拷回给arr中
    }
    public static void margeSort(int[] arr) {
        //参数安全检测
        if (arr == null || arr.length == 1) {
            return;
        }
        for (int i = 1; i < arr.length ; i*=2) {
            marge(arr,i);
        }
    }
    public static void main(String[] args) {
        int[] arr = {26,53,48,67,13,57,32,49,50,60};
        margeSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：