归并排序实现

public class MergeSort{
        //测试程序
    public static void main(String[] args){
        int[] arr = {3,2,1,5,6,2};
        process(arr,0,arr.length-1);
        for(int i = 0;i<arr.length-1;i++){
            System.out.println(arr[i]);
        }
    }
    //使数组的某一段有序
    public static void process(int[] arr,int left,int right){

        if(left==right){
            return;
        }

        //求中点位置，注意移位运算符的优先级比加号的优先级低，所以必须加括号
        int middle = left+((right-left)>>1);
        //使中点左边有序
        process(arr,left,middle);
        //使中点右边有序
        process(arr,middle+1,right);
        //合并左右两段
        merge(arr,left,middle,right);
    }

    public static void merge(int[] arr,int l,int m,int r){

        //辅助数组
        int[] help = new int[r-l+1];
        int i = 0;

        int p1 = l;
        int p2 = m+1;

        while((p1<=m)&&(p2<=r)){
            help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=m){
            help[i++] = arr[p1++];
        }

        while(p2<=r){
            help[i++] = arr[p2++];
        }

        //将辅助数组中的元素copy到原数组之中
        for(int j = 0;j<=help.length-1;j++){
            arr[l+j] = help[j];
        }

    }

}

时间复杂度利用master公式计算得到O(n*logN)