sul*_*ing 12 java algorithm math
我正在查看grepcode上java.util.ArrayList的sort()方法的源代码.他们似乎在小型数组(大小<7)上使用插入排序,并在大型数组上进行合并排序.我只是想知道这是否会产生很大的不同,因为它们只对大小<7的数组使用插入排序.在现代机器上,运行时间的差异几乎不可察觉.
我在Cormen读过这篇文章:
尽管合并排序在O(n*logn)最坏情况下运行,插入排序在O(n*n)最坏情况下运行,但插入排序中的常数因素可以使其在实际中对于许多机器上的小问题大小更快.因此,当子问题变得足够小时,通过在合并排序中使用插入排序来粗化递归的叶子是有意义的.
如果我会为我需要的某个组件设计排序算法,那么在合并排序与运行时间的差异变得明显之前,我会考虑使用insert-sort来获得更大的大小(可能达到<100).
我的问题是,达到<7的大小背后的分析是什么？