归并排序

归并排序的核心思想是分治算法，顾名思义就是，将大问题分成小问题，小问题都解决了，大问题也就解决了。解决分治问题最常用的编程技巧就是递归。
写递归代码的技巧就是，先分析得出递推公式，然后找出终止条件，最后将递推公式翻译成递推代码。
我们先通过一张图来看一下归并算法的思想

image.png

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

其中，merge_sort(p...r)表示对数组中下表为p到r的元素进行排序。我们将这个问题转换为对两个子数组merge_sort(p…q) 和 merge_sort(q+1…r)排序，最好再将排序后的子数组结果合并，得到p到r直接数据的排序结果。
有上面的图我们可以看出，当我们将数组切分到只有一个或者0个元素的时候数组自然就有序了，这时再往上依次合并即可。
下面是java代码实现：

package sort.basic;

import org.junit.Test;

public class MergeSort {
    public void mergeSort(int[] data, int start, int end){
        if (start >= end){
            return;
        }
        int mid = (end - start)/2 + start;
        mergeSort(data, start, mid);
        mergeSort(data, mid + 1, end);
        merge(data, start, mid, end);
    }

    private void merge(int[] data, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int index = 0;
        int start1 = start;
        int start2 = mid + 1;
        while(start1 <= mid || start2 <= end){
            if(start1 > mid){
                while(start2 <= end){
                    temp[index++] = data[start2++];
                }
                break;
            }
            if(start2 > end){
                while(start1 <= mid){
                    temp[index++] = data[start1++];
                }
                break;
            }
            if(data[start1] <= data[start2]){
                temp[index++] = data[start1++];
            }
            else {
                temp[index++] = data[start2++];
            }
        }
        for(int i = start; i <= end; i++){
            data[i] = temp[i - start];
        }
    }

    @Test
    public void sortTest(){
        int[] data = new int[]{11,8,3,9,7,1,2,5};
        mergeSort(data, 0, data.length-1);
        for(int ele : data){
            System.out.print(ele + " ");
        }
        System.out.println();
    }
}

缺点： 观察merge函数，我们发现mergesort的每次合并都需要额外的空间，空间复杂度为O(n).
快速排序 之所以比归并排序应用范围广，就在于其s空间复杂度为O(1)