import java.util.Arrays;

public class mergesort {
	    /** 
	     * 归并排序 
	     * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 
	     * 时间复杂度为O(nlogn) 
	     * 稳定排序方式 
	     */  
	//start起始下标  end最后一位下标
	    public static int[] sort(int[] nums, int start, int end) {  
	        int mid = (start + end) / 2;  
	        if (start < end) {  
	            // 左边  
	            sort(nums, start, mid);  
	            // 右边  
	            sort(nums, mid + 1, end); 
	            // 左右归并  
	            merge(nums, start, mid, end);  
	        }  
	        return nums;  
	    }  
	  
	    public static void merge(int[] nums, int start, int mid, int end) {  
	        int[] temp = new int[end - start + 1];  
	        int i = start;//左序列起始  
	        int j = mid + 1;//右序列起始
	        int k = 0;  
	  
	        // 比较两个有序列，将最小的放入临时序列中  
	        while (i <= mid && j <= end) {  
	            if (nums[i] <= nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	        // 把左边剩余的数移入临时序列 
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	        // 把右边边剩余的数移入临时序列  
	        while (j <= end) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        // 把临时序列中的数覆盖nums数组  
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + start] = temp[k2];  
	        }  
	    }  
	  
	      
	    // 归并排序的实现  
	    public static void main(String[] args) {  
	  
	        int[] nums = { 28, 7, 27, 3, 1, 6, 9, 0, 5, 4 };  
	        mergesort.sort(nums, 0, nums.length-1);  
	        System.out.println("sort:"+Arrays.toString(nums));  
	    }  
	

}