javascript - 在 V8 的 Array.sort 中使用插入排序而不是希尔排序的理由是什么

Question

V8 对于长度超过 10 个元素的数组使用快速排序，对于小于 10 个元素的数组使用插入排序。这是the sources :

function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.

我想知道不使用 shell-sort 而不是插入排序的理由是什么？我知道这对于 10 个元素的数组可能没有什么影响，但仍然如此。有什么想法吗？

Answer 1

最初的理由已被历史遗忘； commit为短数组引入插入排序(早在 2008 年)就只提到它比快速排序(对于此类短数组)更快。所以它归结为:有人以这种方式实现了它，从那以后没有其他人认为有理由改变它。

由于众所周知，InsertionSort 对于短数组非常有效，因此我同意更改它可能不会产生任何影响 - 并且团队需要做很多事情才能真正产生影响。