在 V8 中对 Array.sort 中的 shell 排序使用插入排序的基本原理是什么

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 为短数组引入 InsertionSort（早在 2008 年）只提到它比 QuickSort 更快（对于这样的短数组）。所以它归结为：有人以这种方式实现了它，此后没有其他人看到改变它的理由。

由于已知 InsertionSort 对于短数组非常有效，我同意对其进行更改可能不会产生影响——团队需要做的很多事情实际上确实产生了影响。

Answer 2

好问题。原理很简单，在那些小数组上使用插入排序实际上更快，至少通常是这样。 Java 其实很久以前就做了同样的转换。现在，如果他们的代码中的数组长度小于 7，他们就会进行插入排序。参见 here。它在顶部的函数 sort1 下。

基本上（在大多数情况下）这种小数组发生的情况是，快速排序的开销使其比插入排序慢。在这些情况下，插入排序更有可能在 O(n) 时达到最佳性能，而快速排序仍可能停留在 O(n log n)。

另一方面，

Shell 排序往往比插入排序慢得多。话虽这么说，它可以更快（相对）。插入排序的最佳情况仍然是 0(n)，而 shell 排序的最佳情况是 O(n log n)。从数学的角度来看，十岁以下的所有数字都应该有可能变得更快。不幸的是，对于 shell 排序，涉及更多的交换。 Shell 排序会变得更慢。插入排序往往能够完成 O(1) 次交换的交换，而 Shell 排序可能是 O(n) 次交换。机器中的交换成本很高，因为它们最终往往会使用第三个临时寄存器进行交换（有使用 XOR 的方法，但通常仍然是 CPU 上的三个命令）。因此，通常情况下，插入排序在实际机器上仍然胜出。

在 V8 中对 Array.sort 中的 shell 排序使用插入排序的基本原理是什么

What's the rationale for using insertion sort over shell sort in Array.sort in V8

javascript

arrays

sorting

v8