Java Collections.sort（nodes）使用什么类型？

问题描述：

我认为是MergeSort，它是O（n log n）。

I think it is MergeSort, which is O(n log n).

但是，以下输出不同意：

However, the following output disagrees:

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

我正在排序一个节点4个节点按顺序号，而排序是做6个比较。
我很困惑，因为6>（4 log（4））。有人可以向我解释这个问题吗？

I am sorting a nodelist of 4 nodes by sequence number, and the sort is doing 6 comparisons. I am puzzled because 6 > (4 log(4)). Can someone explain this to me?

PS这是mergesort，但我还是不明白我的结果。

感谢大家的回答。感谢Tom纠正我的数学。

Thanks for the answers everyone. Thank you Tom for correcting my math.

答

O（n log n）并不意味着比较的数量等于或小于n log n，只是所用的时间将与n log n成比例地缩放。尝试使用8个节点，16个节点或32个节点进行测试，并检查时间。

O(n log n) doesn't mean that the number of comparisons will be equal to or less than n log n, just that the time taken will scale proportionally to n log n. Try doing tests with 8 nodes, or 16 nodes, or 32 nodes, and checking out the timing.

Java Collections.sort（nodes）使用什么类型？

相关推荐