如何对较小(子)阵列进行排序使快速排序更快？

Question

我听说在quicksort中最好先在较小的子阵列上调用递归.例如,如果5是数据透视表并且数据被排序到4,1,3,5,7,6那么最好先对子数组进行排序,7,6因为它包含两个元素,其中4,1,3包含三个元素.

所有知识的来源都为快速排序提供了伪代码

quicksort(A, i, k):
  if i < k:
    p := partition(A, i, k)
    quicksort(A, i, p - 1)
    quicksort(A, p + 1, k)

因此,首先实现在较小阵列上递归的算法看起来就像

quicksort(A, i, k):
  if i < k:
    p := partition(A, i, k)
    if(p-i > k-p)
    /*difference from start point to pivot is greater than
   difference from pivot to end point*/
        quicksort(A, p + 1, k)
        quicksort(A, i, p - 1)
   else
        quicksort(A, i, p - 1)
        quicksort(A, p + 1, k)

我用这样的代码编写了用Java编写的代码,它确实看起来更快,但为什么呢？起初我认为它与尾递归优化有关,但后来意识到由于Java不支持它,因此确实是错误的.

为什么要先将较小的子代码中的代码排序更快？这篇文章声称它应该是

Answer 1

Java JIT 编译器可以消除尾递归，从而减少堆栈内存的使用。减少的堆栈内存可以减少缓存压力，从而允许更大的分区大小适应更快的缓存级别。

其他小的改进是减少了函数调用的数量。那些执行的指令数量略有减少。但是，当操作不适合缓存的数据时，指令数减少通常与性能的相关性非常低。