我认为是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))。有人可以向我解释一下吗？
谢谢大家的回答。谢谢汤姆纠正我的数学。
O(n log n) 并不意味着比较次数将等于或小于 n log n，只是所花费的时间将 scale 与 n log n 成比例。尝试使用 8 个节点、16 个节点或 32 个节点进行测试，并检查时序。
你对四个节点进行了排序，所以你没有得到合并排序；排序切换为插入排序。
根据维基百科合并排序文章（已添加重点）：
在 Java 中，Arrays.sort() 方法根据数据类型和实现效率使用合并排序或调整的快速排序当排序的数组元素少于 7 个时切换到 插入排序。
Arrays.sort从 Java 7 开始，Java 的 Oracle 实现转而使用 Python 使用的 timsort：JDK-6804124。
（上面链接的 timsort 专着非常值得一读。）
处理数据量 n 的算法 A(n) 的时间复杂度为 O(f(n))，对于某个函数 f，如果存在两个严格正的常数 C_inf 和 C_sup，使得：
C_inf。 f(n) < ExpectedValue(OperationCount(A(n))) < C_sup . f(n)
有两点需要注意：
实际的常量 C 可以是任何东西，并且 do 取决于操作的相对成本（取决于语言、VM、架构或操作的实际定义）。例如，在某些平台上，+ 和 * 具有相同的成本，而在其他平台上，后者的成本要慢一个数量级。
被称为“O(f(n))”的数量是一个预期操作计数，基于您正在处理的数据的某些可能任意模型。例如，如果您的数据几乎完全排序，则合并排序算法将主要是 O(n)，而不是 O(n . Log(n))。
我写了一些您可能感兴趣的有关 Java 排序算法的内容，并进行了 Collections.sort() 的一些性能测量。目前的算法是一个带有插入排序的归并排序，一旦你的子列表达到一定的大小（注意，这个算法很可能会在 Java 7 中改变）。
您确实应该将 Big O 表示法作为算法总体扩展方式的指示；对于特定的排序，精确的时间将偏离此计算预测的时间（正如您将在我的图表中看到的那样，组合的两种排序算法各自具有不同的性能特征，因此排序的总时间是有点复杂）。
也就是说，作为一个粗略的指导，每次将元素数量加倍时，如果将预期时间乘以 2.2，就不会相差太远。 （不过，对于几个元素的非常小的列表来说，这样做实际上没有多大意义。）