编辑代码

public class Main{

    public static void main(String[] args) {
        int[] sort = new int[9];
        sort[0] = 3;
        sort[1] = 87;
        sort[2] = 1;
        sort[3] = 9;
        sort[4] = 6;
        sort[5] = 38;
        sort[6] = 29;
        sort[7] = 71;
        sort[8] = 76;
        System.out.println("Before Sort:");
        arrayToString(sort);
        mergeSort(sort,0,sort.length - 1);
        System.out.println("After Sort:");
        arrayToString(sort);
    }

	public static void mergeSort(int[] sorted,int left,int right){
		int min = (left + right) / 2;
		if(left < right){
			//将序列分为左右两个子序列
			//再分别对左右两个子序列再分为左右两个子序列
			mergeSort(sorted,left,min);
			mergeSort(sorted,min + 1,right);

			//排序并合并
			int[] temp = new int[right - left + 1];
			int i = left;
			int j = min + 1;
			int k = 0;
			while(i <= min && j <= right){
				if(sorted[i] < sorted[j]){
					temp[k++] = sorted[i++];
				}else{
					temp[k++] = sorted[j++];
				}
			}
			//将左边剩余的数据放入新数组
			while(i <= min){
				temp[k++] = sorted[i++];
			}
			//将右边剩余的数据放入新数组
			while(j <= right){
				temp[k++] = sorted[j++];
			}
			//排好序的新数组覆盖原数组
			for(int n = 0;n < temp.length;n++){
				sorted[n + left] = temp[n];
			}
		}
	}

    public static void arrayToString(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.print("\n");
    }	
    
}