一种常用的归并排序算法--归并排序

本文要介绍的是一种叫做归并排序的排序算法

该算法最坏情况下时间复杂度是O(n log n)具有较低的时间复杂度，但是归并过程中，需要O(n)的辅助空间，是一个稳定的排序算法，但是由于需要额外申请过多的空间，因此实际效果没有快速排序好。

    归并排序根本思想：
    1、先把序列划分成长度基本相等的子序列
    2、对每个子序列归并排序(递归) 直到子序列长度为1(长度为1的子序列当然是有序的)
    3、把排好序的子序列合并成最后的结果

请跟随java代码来认识整个过程：

public class MergeSort {
    public static void mergeSort(int[] arr){
        mergeSort(arr, 0, arr.length-1);
    }
    private static void mergeSort(int[] arr, int start, int end){
        if(start<end){
            int mid = (start+end)>>1;
            mergeSort(arr,start,mid);
            mergeSort(arr,mid+1,end);
            merge(arr,start,mid,end);
        }
    }
    //[start,mid],(mid,end]归并
    private static void merge(int[] arr, int start, int mid, int end){
        int[] newArr = new int[end-start+1];
        int first = start;
        int second = mid + 1;
        int index = 0;
        while(first<=mid&&second<=end){
            if(arr[first]<arr[second])
                newArr[index++] = arr[first++];
            else
                newArr[index++] = arr[second++];
        }
        while(first<=mid)
            newArr[index++] = arr[first++];
        while(second<=end)
            newArr[index++] = arr[second++];
        for(int i = start,j=0; i <= end; i++,j++){
            arr[i] = newArr[j];
        }
    }
}

归并排序时间复杂度较低，最差O(n log n)，但是由于需要O(n)的空间，实际运用不如快速排序。