归并排序

分而治之的思想：即，我把数组不断分两半，分到最后没办法分了，再逐渐的治，所以分治可以将代码分成分和治两个部分

时间复杂度o(nlogn)

java代码如下：

    public static void mergeSort(int[] arr,int start,int end){
        if (start<end){
            int mid=(start+end)/2;
            mergeSort(arr,start,mid);
            mergeSort(arr,mid+1,end);
            mergeArray(arr,start,mid,end);
        }
    }

    public static void mergeArray(int[] arr,int left,int mid,int right){
        int[] tmp=new int[arr.length];
        int p1=left;
        int p2=mid+1;
        int k=left;

        while(p1<=mid&&p2<=right){
            if (arr[p1]<=arr[p2]){
                tmp[k]=arr[p1];
                p1++;
            }else{
                tmp[k]=arr[p2];
                p2++;
            }
            k++;
        }
        while(p1<=mid){
            tmp[k]=arr[p1];
            k++;
            p1++;
        }
        while (p2<=right){
            tmp[k]=arr[p2];
            k++;
            p2++;
        }
        for (int i = left; i <=right ; i++) {
            arr[i]=tmp[i];
        }
    }