归并排序递归实现

/*
 * 归并排序递归实现
 * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。
 * 然后再把有序子序列合并为整体有序序列 
 * 时间复杂度为O(nlogn) 
 * 
 * */

import java.util.Arrays;

public class MegerSort {
    public int[] sort(int[] k,int low,int high)
    {
        int center=(low+high)/2;  //获取数组中间位置
        if(low<high)
        {
            sort(k,low,center);   //对左边进行递归调用
            sort(k,center+1,high);//对右边进行递归调用
            merge(k,low,center,high); //先分成两半，然后再归并起来
        }
        return k;
    }
    public void merge(int[] k,int low, int center,int high)
    {
        int[] temp=new int[high-low+1]; //声明一个可以存放一定大小的数组，
        int i=low; //左边起始位置
        int j=center+1; //右边起始位置
        int m=0; 
        //对左右数组进行比较排序
        while(i<=center && j<=high)
        {
            if(k[i]<k[j])
            {
                temp[m++]=k[i++];
            }
            else 
            {
                temp[m++]=k[j++];
            }
        }
        while(i<=center)  //当左边数组还没遍历完时，直接添加在后面
        {
            temp[m++]=k[i++];
            
        }
        while(j<=high)//当右边数组还没遍历完时，直接添加在后面
        {
            temp[m++]=k[j++];
            
        }
         // 把新数组中的数覆盖k数组  
        for(int n=0;n<temp.length;n++) 
        {
            k[n+low]=temp[n];
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MegerSort sort = new MegerSort();
        int[] A ={5,7,2,9,8,6,1,3,4,0};
        System.out.println("排序前的顺序：");
        System.out.println(Arrays.toString(A));
        sort.sort(A, 0, A.length-1);
        System.out.println();
        System.out.println("使用归并排序后的顺序为");
        System.out.println(Arrays.toString(A));
        
    }

}