使用插入排序的合併排序的修改版本

Question

我使用合併排序分割數組後，直到數組長度爲k，我應該在k長度數組上使用插入排序，然後繼續合併。什麼應該是k的最優值？

另外，我發現與我的類似這些問題，但沒有找到一個明確的答案 Choosing minimum length k of array for merge sort where use of insertion sort to sort the subarrays is more optimal than standard merge sort Modification to merge sort to implement merge sort with insertion sort Java

Answer 1

這個我覺得是我的問題http://atekihcan.github.io/CLRS/P02-01/一個更加合適的回答，在這裏引用它，

對於改進算法具有相同的漸近運行時間作爲標準歸併排序，

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk) 

必須同

Θ(nlgn). 

爲了滿足這個條件，K不能長得比漸近lg⁡n更快（如果k增長，因爲NK任期比lg⁡n快，該算法將運行在比θ（nlgn）更差的漸近時間處。但只是這個論點是不夠的，因爲我們必須檢查

k=Θ(lgn), 

該要求是否成立。

如果我們假定，

k=Θ(lgn), 

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)=Θ(nlgn+nlgn−nlg(lgn))=Θ(2nlgn−nlg(lgn))†=Θ(nlgn) 

†LG（LGN）相比LGN爲充分大的n值是非常小的。

Answer 2

只是衡量。

最佳閾值取決於您的編程語言，數據類型，daata設置值分佈，計算機硬件，合併排序和插入排序實現細節等。

通常這個值在10-200範圍內，最佳值的增益不是很重要。