归并排序算法

1、排序原理

归并排序使用的是分治思想（Divide and Conquer），分治，顾名思义，就是分而治之，是将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

归并排序的核心思想是：如果要排序一个数组，先把数组从中间分成前后两部分，然后再分解，直到每个子序对中只剩一个元素，最后通过递归，层层合并。

2、代码实现

public static int[] mergeSort(int[] array) {
        if (array.length <=1) return array;
        //取数组的中间位置
        int mid = array.length>>1;
        //数组拆分
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        //递归调用
        int[] result=merge(mergeSort(left), mergeSort(right));
        return result;
    }

    /**
     *  合并，
     * @param left  拆分后左侧数组
     * @param right 拆分后右侧数组
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i=0,j=0; // i用来标识左侧数组 ， j用来标识右侧数组
        for (int index = 0; index < result.length; index++) {
            //如果i 大于左侧数组，说明左侧已经没有多余的数组，将剩余的数据拷贝到临时数组
            if (i >= left.length) {
                result[index] = right[j++];
            }
            //如果j大于右侧数组，说明右侧已经没有多余的数组，将剩余的数据拷贝到临时数组
            else if (j >= right.length) {
                result[index] = left[i++];
            }
            //比较两个数组，如果左侧大于右侧数组，就将右侧数组放入到临时数组
            else if (left[i] > right[j]) {
                result[index] = right[j++];
            }
            else{//就将左侧数组放入到临时数组
                result[index] = left[i++];
            }
        }
        return result;
    }

4、算法分析

4.1、时间复杂度

• 最好情况：T(n)=O(nlogn)
• 最坏情况：T(n)=O(nlogn)
• 平均情况：T(n)=O(nlogn)

4.2、是否稳定

归并排序是一种稳定的排序算法。

4.3、是原地排序算法吗？

归并排序的空间复杂度是 O(n)，所以不是原地排序算法