归并排序是JDK对象数组的排序算法之一，接下来开始分析JDK的归并排序算法。
/**
* 将指定范围的对象数组按自然顺序升序排序
*
* Src is the source array that starts at index 0
* Dest is the (possibly larger) array destination with a possible offset
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset to generate corresponding low, high in src
* To be removed in a future release.
*/
@SuppressWarnings({"unchecked", "rawtypes"})
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// 规模很小的数组的排序，直接插入排序的效率反而比归并要高
// 规模定在INSERTIONSORT_THRESHOLD = 7之内
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// 递归排序dest的一半元素并赋值给src
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// 如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并
// 如果需要归并的两端low~(mid-1)，mid~high已经有序，即src[mid-1]==src[mid]，那么只需要将src的low~high赋值对应的dest即可，无需再归并
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// 将src的两个部分合并，并赋值给dest
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}