归并排序

基本思想：将初始序列中的n个对象，看成n个长度为1的有序子序列，先做两两归并，得到int(n/2）个长度为2的归并项（如果n为奇数，则最后一个有序子序列为1）；在做两两归并，重复直到最后得到一个长度为n的有序序列。

图解：

代码实现：

public class MergeSort{
   	//归并排序(升序)
	public static void mergeSort(int[] sorted,int left,int right){
		int min = (left + right) / 2;
		if(left < right){
			//将序列分为左右两个子序列
			//再分别对左右两个子序列再分为左右两个子序列
			mergerSort(sorted,left,min);
			mergerSort(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 main(String[] args) {
        int[] sort = new int[9];
        sort[0] = 2;
        sort[1] = 88;
        sort[2] = 1;
        sort[3] = 8;
        sort[4] = 7;
        sort[5] = 38;
        sort[6] = 28;
        sort[7] = 72;
        sort[8] = 76;
        System.out.println("Before Sort:");
        System.out.println(Arrays.toString(sort));
        MergeSort.mergerSort(sort,0,sort.length - 1);
        System.out.println("After Sort:");
        System.out.print(Arrays.toString(sort));
    }
}

运行结果：