排序算法（4）--归并排序

综上可知：

归并排序其实要做两件事：

（1）“分解”——将序列每次折半划分。

（2）“合并”——将划分后的序列段两两合并后排序。

@Override
public void sort(int[] arr) {
	mergeSort(arr);
}

private void merge(int[] array,int start,int mid,int end){
	int temp[] = new int[end-start+1];//临时数组
	
	int firstArrIndex = start;//第一段数组序列的下标
	int secondArrIndex = mid+1;//第二段数组序列的下标
	int tempArrIndex = 0;//临时存放数组的下标
	
	//1.扫描第一个数组序列和第二个数组序列
	while(firstArrIndex <=mid && secondArrIndex<=end){
		//1.1 当第一段数组小于第二段数组 未排序的首个元素时
		if(array[firstArrIndex] <=array[secondArrIndex]){
			temp[tempArrIndex] = array[firstArrIndex];
			firstArrIndex++;
		}else{//1.2 当第二段数组小于第一段数组 未排序的首个元素时
			temp[tempArrIndex] = array[secondArrIndex];
			secondArrIndex++;
		}
		
		tempArrIndex++;
	}
	
	//2.当第一段没有复制完全时，将剩余的数组全部复制到临时数组
	while(firstArrIndex<=mid){
		temp[tempArrIndex] = array[firstArrIndex];
		firstArrIndex++;
		tempArrIndex++;
	}
	
	
	//3.当第二段没有复制完全时，讲剩余的数组全部复制到临时数组
	while(secondArrIndex<=end){
		temp[tempArrIndex] = array[secondArrIndex];
		secondArrIndex++;
		tempArrIndex++;
	}
	
	//4.将临时数组复制到原始数组
	for(tempArrIndex=0,firstArrIndex=start;firstArrIndex<=end;tempArrIndex++,firstArrIndex++){
		array[firstArrIndex] = temp[tempArrIndex];
	}
}

private void mergeSort(int[] arr){
	for (int gap = 1; gap < arr.length; gap = 2 * gap) {
		int i=0;
		//归并gap长度的两个相邻子数组
		for(i=0; i+2*gap-1< arr.length; i = i + 2*gap) {
			merge(arr, i, i+gap-1, i+2*gap-1);
		}
		
		// 余下不足两个合并的子数组。保证第一个数组gap存在。
		if(i + gap - 1 < arr.length){
			merge(arr, i, i + gap - 1, arr.length - 1);
		}
	}
}