问在Array.sort中对V8中的shell排序使用插入排序的理由是什么

EN

最初的基本原理已被历史所遗忘；为短数组引入InsertionSort的InsertionSort(一直追溯到2008年)只提到它比QuickSort更快(对于这样的短数组)。因此，它归结为:有人以这种方式实现了它，而其他人从那以后就没有看到改变它的理由了。

因为众所周知，InsertionSort对于短数组非常有效，所以我同意更改它可能没有什么区别--而且团队需要做的事情很多--这确实会带来不同的结果。

问得好。理由很简单，对这些小数组使用插入排序实际上更快，至少通常如此。事实上，Java很久以前就做了同样的切换。现在，如果数组在代码中的长度小于7，则进行插入排序。见这里。它在顶部的函数sort1下面。

基本上，对于这样小的数组所发生的事情(在大多数情况下)是，快速排序的开销使得它比插入排序慢。在这些情况下，插入排序更有可能接近O(n)的最佳性能，而快速排序仍然可能停留在O(n log n)。

另一方面，Shell排序往往比插入排序慢得多。尽管如此，它可以更快(相对而言)。插入排序的最佳情况仍然是0( n)，而shell排序的最佳情况是O(n log )。那么，从数学的角度来看，所有十岁以下的数字都有可能变得更快。不幸的是，对于shell排序，需要进行更多的交换。然后，Shell排序可能会变得更慢。插入排序往往能够与O(1)交换进行交换，而Shell排序则可能与O(n)交换有关。交换在机器中是昂贵的，因为它们最终往往使用第三个临时寄存器进行交换(有使用XOR的方法，但CPU上通常仍然有三个命令)。因此，插入排序通常在实际机器上仍然占上风。