Java Collections.sort(节点)使用什么类型？

Question

我认为它是MergeSort,它是O(n log n).

但是,以下输出不同意:

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

我按序列号排序了4个节点的节点列表,排序正在进行6次比较.我很困惑,因为6>(4 log(4)).谁可以给我解释一下这个？

PS这是mergesort,但我仍然不理解我的结果.

感谢大家的答案.谢谢汤姆纠正我的数学.

Answer 1

O(n log n)并不意味着比较次数将等于或小于n log n,只是所花费的时间将按比例缩放到n log n.尝试使用8个节点,或16个节点或32个节点进行测试,并检查时间.

Answer 2

你排序了四个节点,所以你没有得到合并排序; sort切换到插入排序.

在Java中,Arrays.sort()方法根据数据类型使用合并排序或调整快速排序,并且当排序少于七个数组元素时,实现效率切换到插入排序.(维基百科,重点补充)

Arrays.sort由Collections类间接使用.

最近接受的错误报告表明,Sun的Java实现将来会使用Python的时间:http://bugs.sun.com/bugdatabase/view_bug.do？video_id = 6804124

(以上链接的timsort专着非常值得一读.)