Collections.sort

?

事實上Collections.sort方法底層就是調用的Arrays.sort方法，而Arrays.sort使用了兩種排序方法，快速排序和優化的歸并排序。

? ? 快速排序主要是對那些基本類型數據（int,short,long等）排序， 而歸并排序用于對Object類型進行排序。

使用不同類型的排序算法主要是由于快速排序是不穩定的，而歸并排序是穩定的。這里的穩定是指比較相等的數據在排序之后仍然按照排序之前的前后順序排列。對于基本數據類型，穩定性沒有意義，而對于Object類型，穩定性是比較重要的，因為對象相等的判斷可能只是判斷關鍵屬性，最好保持相等對象的非關鍵屬性的順序與排序前一致；另外一個原因是由于歸并排序相對而言比較次數比快速排序少，移動（對象引用的移動）次數比快速排序多，而對于對象來說，比較一般比移動耗時。

public static <T extends Comparable<? super T>> void sort(List<T> list) {list.sort(null);
}

List#sort

default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}
}public static <T> void sort(T[] a, Comparator<? super T> c) {if (c == null) {sort(a);} else {if (LegacyMergeSort.userRequested)legacyMergeSort(a, c);elseTimSort.sort(a, 0, a.length, c, null, 0, 0);}
}public static void sort(Object[] a) {if (LegacyMergeSort.userRequested)legacyMergeSort(a);elseComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

TimSort

結合了歸并排序和插入排序的混合算法，它基于一個簡單的事實，實際中大部分數據都是部分有序（升序或降序）的。

TimSort 算法為了減少對升序部分的回溯和對降序部分的性能倒退，將輸入按其升序和降序特點進行了分區。排序的輸入的單位不是一個個單獨的數字，而是一個個的塊-分區。其中每一個分區叫一個run。針對這些 run 序列，每次拿一個 run 出來按規則進行合并。每次合并會將兩個 run合并成一個 run。合并的結果保存到棧中。合并直到消耗掉所有的 run，這時將棧上剩余的 run合并到只剩一個 run 為止。這時這個僅剩的 run 便是排好序的結果。

綜上述過程，Timsort算法的過程包括

（0）如果數組長度小于某個值，直接用二分插入排序算法

（1）找到各個run，并入棧

（2）按規則合并run

?

/*** Sorts the given range, using the given workspace array slice* for temp storage when possible. This method is designed to be* invoked from public methods (in class Arrays) after performing* any necessary array bounds checks and expanding parameters into* the required forms.** @param a the array to be sorted* @param lo the index of the first element, inclusive, to be sorted* @param hi the index of the last element, exclusive, to be sorted* @param work a workspace array (slice)* @param workBase origin of usable space in work array* @param workLen usable size of work array* @since 1.8*/
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {assert a != null && lo >= 0 && lo <= hi && hi <= a.length;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 mergesif (nRemaining < MIN_MERGE) {int initRunLen = countRunAndMakeAscending(a, lo, hi);binarySort(a, lo, hi, lo + initRunLen);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.*/ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);int minRun = minRunLength(nRemaining);do {// Identify next runint runLen = countRunAndMakeAscending(a, lo, hi);// 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);runLen = force;}// Push run onto pending-run stack, and maybe mergets.pushRun(lo, runLen);ts.mergeCollapse();// Advance to find next runlo += runLen;nRemaining -= runLen;} while (nRemaining != 0);// Merge all remaining runs to complete sortassert lo == hi;ts.mergeForceCollapse();assert ts.stackSize == 1;
}

/*** Creates a TimSort instance to maintain the state of an ongoing sort.** @param a the array to be sorted* @param work a workspace array (slice)* @param workBase origin of usable space in work array* @param workLen usable size of work array*/
private ComparableTimSort(Object[] a, Object[] work, int workBase, int workLen) {this.a = a;// Allocate temp storage (which may be increased later if necessary)int len = a.length;int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;if (work == null || workLen < tlen || workBase + tlen > work.length) {tmp = new Object[tlen];tmpBase = 0;tmpLen = tlen;}else {tmp = work;tmpBase = workBase;tmpLen = workLen;}/** Allocate runs-to-be-merged stack (which cannot be expanded).  The* stack length requirements are described in listsort.txt.  The C* version always uses the same stack length (85), but this was* measured to be too expensive when sorting "mid-sized" arrays (e.g.,* 100 elements) in Java.  Therefore, we use smaller (but sufficiently* large) stack lengths for smaller arrays.  The "magic numbers" in the* computation below must be changed if MIN_MERGE is decreased.  See* the MIN_MERGE declaration above for more information.* The maximum value of 49 allows for an array up to length* Integer.MAX_VALUE-4, if array is filled by the worst case stack size* increasing scenario. More explanations are given in section 4 of:* http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf*/int stackLen = (len <    120  ?  5 :len <   1542  ? 10 :len < 119151  ? 24 : 49);runBase = new int[stackLen];runLen = new int[stackLen];
}

MergeSort

private static void legacyMergeSort(Object[] a) {Object[] aux = 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;// 7// 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++];}
}

總結

小于60：使用插入排序，插入排序是穩定的
????大于60的數據量會根據數據類型選擇排序方式：
?????????基本類型：使用快速排序。因為基本類型。1、2都是指向同一個常量池不需要考慮穩定性。
?????????Object類型：使用歸并排序。因為歸并排序具有穩定性。
????注意：不管是快速排序還是歸并排序。在二分的時候小于60的數據量依舊會使用插入排序