public class Mergesort {
    public static void main(String[] args) {
        int[] array = new int[]{5,2,4,1,6,8,10,7,9,3};
        sort(array);
        for(int i=0;i<array.length;i++){
            System.out.println(array[i]);
        }
    }

    public static void sort(int[] array){
        //temp用于保存临时合并结果
        int[] temp = new int[array.length];
        sort(array,0,array.length-1,temp);
    }

    public static void sort(int[] array,int start,int end,int[] temp){
        if(start < end){
          	//先分
            int mid = (end - start) / 2 + start;
            //递归排序
            sort(array,start,mid,temp);
            sort(array,mid + 1,end,temp);
            //再合
            merge(array,start,end,temp);
        }
    }
    public static void merge(int[] array,int start,int end,int[] temp){
        int mid = (end - start) / 2 + start;
        //左半边指针
        int i = start;
        //右半边指针
        int j = mid + 1;
        //temp指针
        int t = 0;
        while(i <= mid && j <= end){
            if(array[i] <= array[j]){
                temp[t++] = array[i++];
            } else {
                temp[t++] = array[j++];
            }
        }
        //把左半边剩余的放到temp中
        while(i <= mid){
            temp[t++] = array[i++];
        }
        //把右半边剩余的放到temp中
        while(j <= end){
            temp[t++] = array[j++];
        }

        t = 0;
        //将temp移到原数组
        while(start <= end){
            array[start++] = temp[t++];
        }
    }
}