Java Collections.sort（节点）使用什么类型？
我认为它是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，但我仍然不理解我的结果。
谢谢大家的答案。 谢谢汤姆纠正我的数学。
O（n log n）并不意味着比较次数将等于或小于n log n，只是所花费的时间将按比例缩放到n log n。 尝试使用8个节点，或16个节点或32个节点进行测试，并检查时间。
你排序了四个节点，所以你没有得到合并排序; sort切换到插入排序。
在Java中，Arrays.sort（）方法根据数据类型使用合并排序或调整快速排序，并且当排序少于七个数组元素时 ，实现效率切换到插入排序。 （维基百科，重点补充）
Arrays.sort由Collections类间接使用。
最近接受的错误报告表明，Sun的Java实现将来会使用Python的时间点 ： http ： //bugs.sun.com/bugdatabase/view_bug.do？video_id = 6804124
（以上链接的timsort专着非常值得一读。）
对于某些函数f，处理一定量数据n的算法A（n）在O（f（n））中，如果存在两个严格正常数C_inf和C_sup，则：
C_inf。 f（n） 有两点需要注意： 实际常量C可以是任何东西，并且取决于操作的相对成本（取决于语言，VM，体系结构或操作的实际定义）。 例如，在某些平台上，+和*具有相同的成本，在某些平台上，后者的速度要慢一个数量级。 归因于“在O（f（n））中的数量”是预期的操作计数，基于您正在处理的数据的某些可能的任意模型。 例如，如果您的数据几乎完全排序，则合并排序算法将主要是O（n），而不是O（n.Log（n））。
我写了一些你可能对Java排序算法感兴趣的东西， 并对Collections.sort（）进行了一些性能测量 。 目前的算法是一个带有插入排序的mergesort，一旦你达到一定大小的子列表（ 注意，这个算法很可能会在Java 7中发生变化 ）。
你应该把Big O表示法作为算法如何整体扩展的指示; 对于特定的类型，精确的时间将偏离此计算预测的时间（正如您在我的图表中看到的，组合的两种排序算法各自具有不同的性能特征，因此排序的总时间是有点复杂）。
也就是说，作为一个粗略的指南，每当你将元素数量加倍时，如果你将预期时间乘以2.2，你就不会太远了。 （但是，对于一些非常小的元素列表来说，这真的没有多大意义。）