有理由期望您在 运行时 不能做得比O（N log N）好。

但是，有趣的部分是研究您是否可以就地，稳定地对其进行分类，最坏情况下的行为等等。

Putty名望的Simon Tatham解释了如何使用merge
sort对链表进行排序。他总结了以下评论：

像任何自重排序算法一样，它的运行时间为O（N log N）。因为这是Mergesort，所以最坏情况下的运行时间仍然是O（N log
N）。没有病理病例。

辅助存储需求小且恒定（即排序例程中的一些变量）。由于数组中链表的本质不同，Mergesort实现避免了通常与算法相关的O（N）辅助存储成本。

C语言中还有一个示例实现，可用于单链表和双链表。

就像@JørgenFogh在下面提到的那样，big-O表示法可能会隐藏一些恒定因素，这些因素可能会导致一种算法由于内存局部性，项目数量少等原因而表现更好。