一、排序思想
将两个或两个以上的一排序文件合并成一个有序文件的过程叫归并，而归并排序就是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将以有序的了序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为“二路归并”。
二、图解案例
三、代码实现
/**
* 归并排序序演示
*
* @author Lvan
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; mergeSort2Down(arr, 0, arr.length - 1); for (int i : arr) {
System.out.print(i + "\t");
}
} /**
* 分发器/汇聚器
*
* @param arr 待排序列
* @param start 待排序列起始值
* @param end 待排序列结束值
*/
private static void mergeSort2Down(int[] arr, int start, int end) {
if (arr == null || start >= end) {
return;
} //获取待排序列中间位置
int mid = (start + end) / 2; //递归排序左边[start,mid]集合
mergeSort2Down(arr, start, mid);
//递归排序右边[mid+1,end]集合
mergeSort2Down(arr, mid + 1, end); //合并左边与右边的有序集合
merge(arr, start, mid, end);
} /**
* 将两个有序序列合并
*
* @param arr 待排序列
* @param start 待排序列开始值
* @param mid 待排序列中间位置索引
* @param end 待排序列结束值
*/
private static void merge(int[] arr, int start, int mid, int end) {
//temp用于汇总2个有序集合的临时集合
int[] temp = new int[end - start + 1];
//第1个有序集合索引
int i = start;
//第二个有序集合索引
int j = mid + 1;
//临时集合索引
int k = 0; //将2个有序集合，插入到临时集合temp中
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
} while (i <= mid) {
temp[k++] = arr[i++];
} while (j <= end) {
temp[k++] = arr[j++];
} //将temp中的数据放入arr集合中
for (i = 0; i < k; i++) {
arr[start + i] = temp[i];
}
}
}