归并排序

归并排序算法的运作如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

归并排序复杂度分析

时间复杂度O(nlogN)*

源码

public class MergeSort{
    public static void mergeSort(int[] arr){
        if(arr.length < 2 || arr == null){
            return;
        }
        sortProcess(arr,0,arr.length-1);
    }
    
    public static void sortProcess(int[] arr,int l,int r){
        if( l == r){
            return;
        }
        int mid = (l+r)/2;
        sortProcess(arr,l,mid);
        sortProcess(arr,mid+1,r);
        
        merge(arr,l,r,mid);
    }
    
    public static void merge(int[] arr,int l,int r,int mid){
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = mid+1;
        while(p1 <= mid && p2 <=r ){
            help[i++] = arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
        }
        
        //两个有且只有一个越界
        while(p1<=mid){
            help[i++] = arr[p1++];
        }
        
        while(p2 <=r){
            help[i++] = arr[p2++];
        }
        
        for(i=0; i<help.length ; i++) {
            arr[l+i] = help[i];
        }
    }
}