在Arrays.java中的sort中
public static void sort(Object[] a, int fromIndex, int toIndex) {if (LegacyMergeSort.userRequested)legacyMergeSort(a, fromIndex, toIndex);elseComparableTimSort.sort(a, fromIndex, toIndex);}/** To be removed in a future release. */private static void legacyMergeSort(Object[] a,int fromIndex, int toIndex) {rangeCheck(a.length, fromIndex, toIndex);Object[] aux = copyOfRange(a, fromIndex, toIndex);mergeSort(aux, a, fromIndex, toIndex, -fromIndex);}/*** Tuning parameter: list size at or below which insertion sort will be* used in preference to mergesort.* To be removed in a future release.*/private static final int INSERTIONSORT_THRESHOLD = 7;/*** 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.*/private static void mergeSort(Object[] src,Object[] dest,int low,int high,int off) {int length = high - low;// Insertion sort on smallest arraysif (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;}// Recursively sort halves of dest into srcint 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);// 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;}// Merge sorted halves (now in src) into destfor(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++];elsedest[i] = src[q++];}}
