一，概述

書接前文【Java】Arrays.sort:DualPivotQuicksort-CSDN博客

Arrays.sort對基本數據類型使用了雙軸快速排序，但是對Object[]類型，則使用了TimSort，TimSort是穩定的排序，它整合了插入排序+歸并排序，存在空間換時間策略，本文簡單解析下此算法實現。

二，實現

入口，Object[]調用Arrays.sort方法

sort內部根據配置策略，使用舊版歸并排序，或TimSort，

進入第二個分支，以下sort算法即TimSort，本篇文章分析核心。

TimSort是插入排序+歸并排序結合的算法，兼顧了兩種排序的優點，比如插入排序時間復雜度最優可以達到O（N），但最差O(N^2)。歸并排序是穩定排序，時間復雜度是O(NLogN)，空間復雜度O(N)，TimSort結合了兩種排序優缺點，時間復雜度在O（N）~O(NLogN)，空間復雜度是O(N)。

此sort算法分步驟進行如下：

1，計算序列最小分塊長度

2，對序列分塊進行線性掃描，得到N塊有序序列

3，對有序序列進行合并

4，當有序序列最后只剩1塊，排序完成，

接下來，看下java內部實現

1，拿到序列size，保存至nRemaining，表示剩余序列長度

2，如果序列長度小于最小分塊MIN_MERGE（32），則直接使用插入排序，此處插入排序用的binarySort，算是對查詢優化，即插入新item時，會通過二分查找算法快速找到插入位置，這里就簡單理解為插入排序即可。

當nRemaining >= MIN_MERGE時，開始計算最小分塊個數

minRunLength是返回最小分塊長度，由以上注釋知，

minRunLength = n (n < MIN_MERGE) or?

MIN_MERGE/ 2 <=?minRunLength <= MIN_MERGE，使得得到的序列個數n/k接近2的冪數，

此處不贅述

下一步，對最小分塊進行排序，

1，線性掃描一遍，簡單將指針經過序列排序，

2，如果得到的runLen長度（已有序塊）< 最小分塊長度，則調用插入排序重新排序，否則就忽略，

這個runLen可能是1，也可能是整個序列長度（序列原本有序），經過以上步驟，會將原序列分成N個有序序列，

下一步，將掃描有序序列入棧，并且合并，如下

棧使用數組記錄，保存了每個分塊的起點位置和長度，

mergeCollapse可能對stack中分組進行合并，合并算法不贅述，

最后，當整個序列合并完成后，stack中只存在一個序列，done