通過jdk6中的Collections源碼可以看到，在sort時(shí)是調(diào)用了Arrays的sort方法，完成排序再返回list
public static void sort(Object[] a) {
Object[] aux = (Object[])a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; ilow &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// 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);
// 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 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++];
}
}
而Arrays.sort()，對原始類型(int[],double[],char[],byte[])，JDK6里用的是快速排序，對于對象類型(Object[])，JDK6則使用歸并排序。
到了jdk7,快速排序升級為雙基準(zhǔn)快排(雙基準(zhǔn)快排 vs 三路快排)；歸并排序升級為歸并排序的改進(jìn)版TimSort。
再到了JDK8， 對大集合增加了Arrays.parallelSort()函數(shù)，使用fork-Join框架，充分利用多核，對大的集合進(jìn)行切分然后再歸并排序，而在小的連續(xù)片段里，依然使用TimSort與DualPivotQuickSort。
談到優(yōu)化過程，先來回憶一下歸并排序，長度為1的數(shù)組是已經(jīng)排序好的。對長度為n>1的數(shù)組，將其分為2段(partition)（最常見的做法是從中間分開）。對兩段數(shù)組遞歸進(jìn)行歸并排序，完成后將其合并（merge）：通過掃描個(gè)已排序的數(shù)組并總是挑出兩者中較小數(shù)作為合并數(shù)組中的下一個(gè)元素，來將兩個(gè)已排序數(shù)組合并形成一個(gè)更大的已排序數(shù)組。
此時(shí)如果我們遇到這樣一個(gè)數(shù)組，{5, 6, 7, 8, 9, 10, 1, 2, 3}，我們利用快排或者歸并帶來的開銷，似乎都不劃算，因?yàn)檎б豢粗恍枰徊骄湍芡瓿膳判?。這也是timSort的一個(gè)主要優(yōu)勢，適應(yīng)性排序，先把5至10截取，1之3截取成兩段，之后再歸并排序，再來看一個(gè)數(shù)組，{64, 32, 16, 8, 4, 2, 1}，對于這樣的案例，通過適應(yīng)性排序的思路，直接反轉(zhuǎn)，再來檢查，已經(jīng)不需要額外的工作了。TimSort在此基礎(chǔ)上還進(jìn)行了其他的一些優(yōu)化，這也助推了該算法的成功。下面我們通過源碼來進(jìn)一步了解一下。
static void sort(T[] a, int lo, int hi, Comparator c) {
if (c == null) {
Arrays.sort(a, lo, hi);
return;
}
rangeCheck(a.length, lo, hi);
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort ts = new TimSort<>(a, c);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
首先是非空的判斷，如果沒有提供comparator,會調(diào)用Arrays.sort,其實(shí)也是ComparableTimSort，后面是算法的主體：如果元素個(gè)數(shù)小于2,直接返回，因?yàn)檫@兩個(gè)元素已經(jīng)排序了
如果元素個(gè)數(shù)小于一個(gè)閾值（默認(rèn)為)，調(diào)用 binarySort，這是一個(gè)不包含合并操作的 mini-TimSort。
在關(guān)鍵的 do-while 循環(huán)中，不斷地進(jìn)行排序，合并，排序，合并，一直到所有數(shù)據(jù)都處理完。
然后會找出run的最小長度，少于這個(gè)最小長度就需要對其進(jìn)行擴(kuò)展，再來看下binarySort
private static void binarySort(T[] a, int lo, int hi, int start,
Comparator c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
T pivot = a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that"s why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
binarySort 對數(shù)組 a[lo:hi] 進(jìn)行排序，并且a[lo:start] 是已經(jīng)排好序的。算法的思路是對 a[start:hi] 中的元素，每次使用 binarySearch 為它在 a[lo:start] 中找到相應(yīng)位置，并插入。
另一個(gè)關(guān)鍵函數(shù)是mergeCollapse
/**
* Examines the stack of runs waiting to be merged and merges adjacent runs
* until the stack invariants are reestablished:
*
* 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
* 2. runLen[i - 2] > runLen[i - 1]
*
* This method is called each time a new run is pushed onto the stack,
* so the invariants are guaranteed to hold for i < stackSize upon
* entry to the method.
*/
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break; // Invariant is established
}
}
}
它會把已經(jīng)排序的 run 合并成一個(gè)大 run，此大 run 也會排好序。并的過程會一直循環(huán)下去，一直到注釋里提到的循環(huán)不變式得到滿足。
合并的時(shí)候，有會特別的技巧。假設(shè)兩個(gè) run 是 run1,run2 ，先用 gallopRight在 run1 里使用 binarySearch 查找 run2 首元素 的位置 k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后，在 run2 中查找 run1 尾元素 的位置 len2 ，那么 run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后，根據(jù)len1 與 len2 大小，調(diào)用 mergeLo 或者 mergeHi 將剩余元素合并。
篇幅限制，不能全都說完了，感興趣的讀者可以移步TimeSort in java 7
