通過jdk6中的Collections源碼可以看到，在sort時是調用了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,快速排序升級為雙基準快排(雙基準快排 vs 三路快排)；歸并排序升級為歸并排序的改進版TimSort。
再到了JDK8， 對大集合增加了Arrays.parallelSort()函數，使用fork-Join框架，充分利用多核，對大的集合進行切分然后再歸并排序，而在小的連續片段里，依然使用TimSort與DualPivotQuickSort。
談到優化過程，先來回憶一下歸并排序，長度為1的數組是已經排序好的。對長度為n>1的數組，將其分為2段(partition)（最常見的做法是從中間分開）。對兩段數組遞歸進行歸并排序，完成后將其合并（merge）：通過掃描個已排序的數組并總是挑出兩者中較小數作為合并數組中的下一個元素，來將兩個已排序數組合并形成一個更大的已排序數組。
此時如果我們遇到這樣一個數組，{5, 6, 7, 8, 9, 10, 1, 2, 3}，我們利用快排或者歸并帶來的開銷，似乎都不劃算，因為乍一看只需要一步就能完成排序。這也是timSort的一個主要優勢，適應性排序，先把5至10截取，1之3截取成兩段，之后再歸并排序，再來看一個數組，{64, 32, 16, 8, 4, 2, 1}，對于這樣的案例，通過適應性排序的思路，直接反轉，再來檢查，已經不需要額外的工作了。TimSort在此基礎上還進行了其他的一些優化，這也助推了該算法的成功。下面我們通過源碼來進一步了解一下。
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,會調用Arrays.sort,其實也是ComparableTimSort，后面是算法的主體：如果元素個數小于2,直接返回，因為這兩個元素已經排序了
如果元素個數小于一個閾值（默認為)，調用 binarySort，這是一個不包含合并操作的 mini-TimSort。
在關鍵的 do-while 循環中，不斷地進行排序，合并，排序，合并，一直到所有數據都處理完。
然后會找出run的最小長度，少于這個最小長度就需要對其進行擴展，再來看下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 對數組 a[lo:hi] 進行排序，并且a[lo:start] 是已經排好序的。算法的思路是對 a[start:hi] 中的元素，每次使用 binarySearch 為它在 a[lo:start] 中找到相應位置，并插入。
另一個關鍵函數是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
}
}
}
它會把已經排序的 run 合并成一個大 run，此大 run 也會排好序。并的過程會一直循環下去，一直到注釋里提到的循環不變式得到滿足。
合并的時候，有會特別的技巧。假設兩個 run 是 run1,run2 ，先用 gallopRight在 run1 里使用 binarySearch 查找 run2 首元素 的位置 k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后，在 run2 中查找 run1 尾元素 的位置 len2 ，那么 run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后，根據len1 與 len2 大小，調用 mergeLo 或者 mergeHi 將剩余元素合并。
篇幅限制，不能全都說完了，感興趣的讀者可以移步TimeSort in java 7
