如果數組長度小於某個閾值，Java 6的mergedortort實現在Arrays.java中使用插入排序。該值被硬編碼爲7.由於算法是遞歸的，對於大型數組，這最終會發生多次。規範merge-sort algorithm不會這樣做，只需使用合併排序，直到列表中只有一個元素。爲什麼Java 6 Arrays＃sort（Object []）從mergesort更改爲insertionsort用於小數組？
這是優化嗎？如果是這樣，它應該如何幫助？爲什麼7？插入排序（甚至是<=7的東西）增加了大量排序所需的比較次數 - 所以會增加成本，其中compareTo()調用速度較慢。
（x軸是size of array，y軸是# of comparisons，對於INSERTIONSORT_THRESHOLD不同的值）
是的，這是故意的。雖然mergesort的Big-O小於插入排序等二次排序，但它所做的操作更復雜，因此速度更慢。
考慮對長度爲8的數組進行排序。除了7次合併操作之外，合併排序還會對自身進行〜14次遞歸調用。每次遞歸調用都會爲運行時帶來一些不重要的開銷。每個合併操作都涉及到一個循環，其中索引變量必須被初始化，遞增和比較，臨時數組必須被複制等。總而言之，您可以預期300多個「簡單」操作。
另一方面，插入排序本質上很簡單，並且使用大約8^2 = 64個操作，其速度更快。
想想這樣。當您手動對10個數字進行排序時，您是否使用合併排序？不，因爲你的大腦在做像插入排序這樣簡單的事情方面要好得多。但是，如果我給了你一年的排序100,000個數字的列表，你可能更傾向於合併排序。
至於神奇數字7，它是憑經驗導出是最佳的。
編輯：在標準插入排序的8個元素中，最壞的情況導致〜36個比較。在規範的合併排序中，你有〜24個比較。增加方法調用的開銷和操作的複雜性，插入排序應該更快。此外，如果您查看平均情況，插入排序將比36更少地進行比較。
對複雜性的這種解釋使得直覺上有很多意義 - 雖然我無法證明7的任何優點，但> 25確實有所作爲。 –
編輯我的答案。我不能100％確定你的基準測試顯示的是你的座標軸沒有被標記。 – tskuzzy
+1如果您需要對很多小陣列進行排序，這會產生非常大的差異。我感覺到了這一點在我自己的皮膚上。 –
我的理解是，這是一個實驗導出的值，其中需要用於插入的時間儘管可能需要更多數量的比較，但排序實際上更低。這是因爲在合併末尾附近，數據可能是幾乎排序的，這使得插入排序表現良好。
我猜是這樣，太。但是當我運行一些基準時，我發現事實並非如此。對於便宜的compareTo操作，任何小於約20的數字大致相當，而對於昂貴的compareTos，比較時間占主導地位。 –
馬修：需要注意的是昂貴的'compareTo'實現是可能不是最常見的情況（記住，Java的基礎類庫是非常通用的，而不是專門迎合正是你的使用情況），並通過使用你也可以小的子列表插入排序節省重複應用D＆C算法或合併排序的開銷。 – Joey
@Matthew Joey對Java BCL的「一般目的」是正確的。另一點需要注意的是，真正昂貴的'compareTo（）'方法應該可以修復，因爲比較兩個對象不需要很長時間。如果沒有辦法避免這種情況發生（可能是因爲對象確實很複雜），可能需要在相關標準上對一組代理對象進行排序（因爲很少會在排序時考慮對象的每個* facet ） – dlev
插入排序爲n（n-1）/ 2，合併排序爲n *（以n爲底數2的log n）。
考慮到這點 -
從以上數據是清除，直到長度爲6，排序速度更快，並且在7之後，合併排序是有效的。
這就解釋了爲什麼使用7。
，這是什麼圖形的來源？你似乎在展示它沒有任何評論 –
我通過排序對象的數組，其計數的compareTo被調用的次數和不同INSERTIONSORT_THRESHOLD使這個圖形。 –
值得注意的是，Java7也有Timsort，它是Tim Peters爲python開發的混合插入。 http://download.java.net/jdk7/docs/api/java/util/Arrays.html#sort%28java.lang.Object [] – Tremmors