为什么Java 6 Arrays#sort(Object [])从mergesort更改为insertionsort用于小数组？

Question

Arrays.java如果数组长度小于某个阈值,Java 6的mergesort实现将使用insert -sort.此值被硬编码为7.由于算法是递归的,因此对于大型数组,这最终会发生多次.规范的合并排序算法不会这样做,只是使用merge-sort一直向下,直到列表中只有1个元素.

这是优化吗？如果是这样,它应该如何帮助？为什么7？插入排序(甚至是<=7事物)会大大增加对大型数组进行排序所需的比较次数 - 因此会增加compareTo()调用速度慢的排序成本.

(x轴是size of array,y轴是# of comparisons,对于不同的值INSERTIONSORT_THRESHOLD)

Answer 1

是的,这是故意的.虽然mergesort的Big-O小于插入排序等二次排序,但它所做的操作更复杂,因此更慢.

考虑对长度为8的数组进行排序.除了7次合并操作外,合并排序还会对自身进行~14次递归调用.每个递归调用都会给运行时带来一些非平凡的开销.每个合并操作都涉及一个循环,其中必须初始化,递增和比较索引变量,必须复制临时数组等.总而言之,您可以期待超过300个"简单"操作.

另一方面,插入排序本质上很简单,并且使用大约8 ^ 2 = 64次操作,这要快得多.

这样想吧.当您手动对10个数字列表进行排序时,是否使用合并排序？不,因为你的大脑在做插入排序之类的简单事情方面要好得多.但是,如果我给你一年的时间来排序100,000个数字的列表,你可能更倾向于合并它.

至于幻数7,根据经验推导出最佳.

编辑:在8个元素的标准插入类型中,最坏的情况导致~36个比较.在规范合并排序中,您有~24个比较.从方法调用和操作复杂性中增加开销,插入排序应该更快.另外,如果你看一下平均情况,插入排序会比36更少的比较.