在经典的合并排序算法中，在将元素重新合并在一起之前，通常会划分输入数组，直到它们具有几个单元素子数组。但是，众所周知，您可以通过拆分数组来修改此合并排序算法，直到您拥有 k 个子数组，每个子数组的大小为 n/k（n 是数组的原始长度）。然后，您可以使用插入排序对这 k 个子数组中的每一个进行排序，并使用 merge 子例程将它们合并。
直觉上，我认为在某些情况下这应该比合并排序更好，因为插入排序在小数组上很快。但我想准确地弄清楚这种混合算法何时优于常规合并排序算法。我不认为小 k 会更好，因为当 k 接近 1 时，我们只会使用插入排序算法。我认为有一些最佳比率 n/k，但我不太确定如何找到它。
任何帮助表示赞赏。