两个有序序列的合并
给出两个有序序列L1,L2，将它们合并为一个有序序列是很简单的，方法如下：
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| L1 | 3 | 4 | 5 | 8 | 9 |
| L2 | 0 | 1 | 2 | 6 | 7 |
同时遍历两个序列，比较两个序列的值，将较小的序列值填入你的目标序列L3并将该序列下标右移，比如L1[0] > L2[0]，就把L2[0] = 0填入L3[0]，然后再比较L1[0],L2[1]，以此类推。最终将得到合并序列L3。
递归完成合并排序
长度为1的序列，可以认为是有序，那么就可以将一个无序序列分解到长度为1的序列进行合并，这个过程可以递归实现。递归的思路就是将无序序列一分为二，分别求解两个无序序列的排序结果，然后对两个序列进行合并，进而最终分解为两个长度为1的序列进行合并。
Code
public static void mergeSort(int[] a, int low, int high) {
int length = high - low;
if (length == 1) return;
int mid = (low + high) >>> 1;
mergeSort(a, low, mid);
mergeSort(a, mid, high);
int[] mergeTo = new int[length];
for (int i = low, j = mid, k = 0; i < mid || j < high;) {
if (i < mid && (j == high || a[i] < a[j])) {
mergeTo[k++] = a[i++];
} else {
mergeTo[k++] = a[j++];
}
}
for (int i = 0; i < mergeTo.length; i++) {
a[low + i] = mergeTo[i];
}
}
