归并排序

归并排序算法的思想并不难理解，只是整个实现过程用到了递归，如果想要理解清楚代码的执行过程还是得费点功夫。

归并排序算法用到了分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。对应到排序这件事，将要排序的数组不断的切分成小的数组，然后将小的数组排完序之后合并起来。

上面是比较正规的说法，不正规的说法是这样的。假设有两个已经排好序的数组A、B，需要将他们合并成一个数组，应该怎么操作？先创建一个空的数组，然后比较A和B最左边的元素大小，将小的元素取出来放到数组中，然后不断的重复上面的操作，直到其中的一个数组被取空了，最后将没有取空的数组中的剩余元素全部拿出来放到大数组中。

A:[1,3,6,7,9]  B:[2,4,5,8,10,15,18]      temp:[]
A:[3,6,7,9]    B:[2,4,5,8,10,15,18]      temp:[1]
A:[3,6,7,9]    B:[4,5,8,10,15,18]        temp:[1,2]
A:[6,7,9]      B:[4,5,8,10,15,18]        temp:[1,2,3]
...
A:[]  B:[10,15,18]      temp:[1,2,3,4,5,6,7,8,9]
A:[]  B:[]              temp:[1,2,3,4,5,6,7,8,9,10,15,18]

接下来，我们只要将需要排序的数组变成A和B那样排好序的小数组就好了。当然我们无法保证每次拿到的数组都恰好可以一刀下去变成两个有序的数组，不过，十个有序的数组也行，实在不行，比十多的有序数组我们也不介意。好了，直接给他切成多个只有一个元素的数组得了，每个数组都有序吧。

代码

1.下面就是将数组切分的部分：

public int[] sort(int[] arr,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            //切割数组的左半部分
            sort(arr,low,mid);
            //切割数组的右半部分
            sort(arr,mid+1,high);
            //左右归并
            merge(arr,low,mid,high);
        }
        return arr;
}

//上面的递归函数，如果从栈的角度理解可能会好一点。
//sort左1-sort右1-merge1-sort左2-sort右2-merge2。。。
//栈顶上的数组为只有一个元素的数组，随着不断的出栈，数组就会越来越大，变成一个有序的大数组

2.这是将切碎后的数组合并的部分：

public void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high-low+1];
    int i= low;
    int j = mid+1;
    int k=0;
    // 把较小的数先移到新数组中
    while(i<=mid && j<=high){
        if(arr[i]<arr[j]){
            temp[k++] = arr[i++];
        }else{
            temp[k++] = arr[j++];
        }
    }
    // 把左边剩余的数移入数组 
    while(i<=mid){
        temp[k++] = arr[i++];
    }
    // 把右边边剩余的数移入数组
    while(j<=high){
        temp[k++] = arr[j++];
    }
    // 把新数组中的数覆盖nums数组
    for(int x=0;x<temp.length;x++){
        arr[x+low] = temp[x];
    }
}

通过稳定性、时间复杂度、空间复杂度三个方面分析一下归并排序：

1.稳定性
可以看得出，值相等的元素的顺序在经过切割合并之后依然保持着不变，也就是说归并排序是稳定的。

2.时间复杂度
首先能够看出来，merge() 的时间复杂度为O(n)。
我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。所以归并排序的时间复杂度为：

T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1

将上的式子进行分解：

T(n) = 2*T(n/2) + n   
      //数组的两个子数组进行合并
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
      //括号中表示两个四分之一数组合成为一个二分之一数组
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=。将k值代入上面的公式，得到T(n)=Cn+n，用大O标记法来表示就是 O(n)。？？
归并排序的执行效率与要排序的原始数组的有序度无关，所以它的最好情况、最坏情况、平均情况都是O(n)。

空间复杂度
在执行merge()的时候会临时申请一个大小为n的数组，当merge()出栈的时候会将数组释放掉，由于整个排序的过程是递归进行，所以这个临时数组就处在一个不断被创建和释放的过程，但是数组的大小始终不会超过n，所以空间复杂度为O(n)。