常见的排序算法之：归并排序

1.原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.实现

1）递归实现

	public static void mergeSort(int[] array) {
        //借助一个辅助数组帮助完成排序
        int[]helper=new int[array.length];
        mergeSortInternal(array, 0, array.length-1,helper);
    }
    //分组
    private static void mergeSortInternal(int[] array, int left, int right,int[]helper) {
        if(left>=right){
            return;
        }
        //分治
        int mid=(left+right)/2;
        //分别对[left,mid]和[mid+1,right]小数组排序
        mergeSortInternal(array,left,mid,helper);
        mergeSortInternal(array,mid+1,right,helper);
        //归并  小数组都有序时
        merge(array,left,mid,right,helper);

    }
    //合并数组
    private static void merge(int[] array, int left, int mid, int right,int[]helper) {
        int begin1=left, end1=mid;
        int begin2=mid+1, end2=right;
        int index=left;

        while(begin1<=end1&&begin2<=end2){
            if(array[begin1]<array[begin2]){
                helper[index++]=array[begin1++];
            }else{
                helper[index++]=array[begin2++];
            }
        }

        while(begin1<=end1)
            helper[index++]=array[begin1++];
        while(begin2<=end2)
            helper[index++]=array[begin2++];
        //拷贝
        for(int i=left;i<=right;i++){
            array[i]=helper[i];
        }
    }

2）迭代实现

public static void mergeNul(int[]arr){
        int []helper=new int[arr.length];
        for(int i=1;i<arr.length;i=i*2){
            //i表示每次归并元素的个数
            for(int j=0;j<arr.length;j+=2*i){
                //j表示归并时的起始位置
                int left=j;
                int mid=j+i-1;
                //右半部分没有数据，不用进行归并
                if(mid>=arr.length-1){
                    continue;
                }
                int right=j+2*i-1;
                if(right>arr.length-1){
                    right=arr.length-1;
                }
                merge(arr,left,mid,right,helper);
            }
        }
    }

3.性能分析

时间复杂度：O(nlog(n))
稳定性：稳定
空间复杂度：O(n) 需要辅助空间对元素进行归并，不能原地归并