我很好奇O（n log n）是链表最好的。
在运行时间期望你不能比O（N log N）做得更好是合理的。
然而，有趣的部分是调查你是否可以对它进行排序in-place，stably，它的最坏情况行为等等。
Putty成名的Simon Tatham解释了如何使用sort a linked list with merge sort。他最后总结了以下评论：
与任何自尊排序算法一样，它具有运行时间O（N log N）。因为这是Mergesort，最坏情况下的运行时间仍为O（N log N）;没有病理病例。
辅助存储要求很小且恒定（即排序例程中的一些变量）。由于链接列表与数组的固有不同行为，此Mergesort实现避免了通常与算法相关的O（N）辅助存储成本。
C中还有一个示例实现，适用于单链接和双链接列表。
正如@JørgenFogh在下面提到的那样，big-O表示法可能会隐藏一些常数因素，这些因素会导致一个算法由于内存局部性而更好地执行，因为项目数量较少等。
Here's an implementation只遍历列表一次，收集运行，然后以mergesort的方式调度合并。
复杂度为O（n log m），其中n是项目数，m是运行次数。最好的情况是O（n）（如果数据已经排序），最坏的情况是O（n log n），如预期的那样。
它需要O（log m）临时存储器;排序在列表上就地完成。
（在下面更新。评论者提出了一个很好的观点，我应该在这里描述）
算法的要点是：
while list not empty
accumulate a run from the start of the list
merge the run with a stack of merges that simulate mergesort's recursion
merge all remaining items on the stack
累积运行不需要太多解释，但是抓住机会积累上升运行和下降运行（反向）是很好的。这里它预先设置小于运行头部的项目，并附加大于或等于运行结束的项目。 （请注意，prepending应使用严格小于保持排序稳定性。）
这里粘贴合并代码最简单：
int i = 0;
for ( ; i < stack.size(); ++i) {
if (!stack[i])
break;
run = merge(run, stack[i], comp);
stack[i] = nullptr;
}
if (i < stack.size()) {
stack[i] = run;
} else {
stack.push_back(run);
}
考虑对列表进行排序（d a g i b e c f j h）（忽略运行）。堆栈状态如下：
[ ]
[ (d) ]
[ () (a d) ]
[ (g), (a d) ]
[ () () (a d g i) ]
[ (b) () (a d g i) ]
[ () (b e) (a d g i) ]
[ (c) (b e) (a d g i ) ]
[ () () () (a b c d e f g i) ]
[ (j) () () (a b c d e f g i) ]
[ () (h j) () (a b c d e f g i) ]
然后，最后，合并所有这些列表。
请注意，stack [i]中的项目（运行）数量为零或2 ^ i，堆栈大小由1 + log2（nruns）限制。每个元素在每个堆栈级别合并一次，因此进行O（n log m）比较。 Timsort在这里与Timsort有相似之处，尽管Timsort使用像Fibonacci序列这样使用2的幂来保持其堆栈。
累积运行利用任何已排序的数据，因此对于已排序的列表（一次运行），最佳情况复杂度为O（n）。由于我们正在累积上升和下降运行，因此运行将始终至少为长度2.（这会将最大堆栈深度减少至少一个，从而首先支付查找运行的成本。）最坏情况复杂性是正如预期的那样，O（n log n）用于高度随机化的数据。
（嗯...第二次更新。）
或者只是看看bottom-up mergesort上的维基百科。
您可以将其复制到数组中然后对其进行排序。
所以它会是O（nlgn）。
请注意，如果您不知道链表中的元素数，则不会知道数组的大小。如果您使用java进行编码，则可以使用Arraylist。
Mergesort是您在这里可以做的最好的。
根据许多因素，将列表复制到数组然后使用Quicksort实际上可能会更快。
这可能更快的原因是数组具有比链表更好的缓存性能。如果列表中的节点分散在内存中，则可能会在整个位置生成缓存未命中。然后，如果数组很大，你仍然会得到缓存未命中。
Mergesort更好地并行化，因此如果您想要的话，它可能是更好的选择。如果直接在链表上执行它也会快得多。
由于两种算法都在O（n * log n）中运行，因此做出明智的决定将涉及在您想要运行它们的机器上对它们进行分析。
---编辑
我决定测试我的假设并编写了一个C程序，它测量时间（使用clock()）对一个链接的整数列表进行排序。我尝试了一个链表，其中每个节点都分配了malloc()和一个链表，其中节点在一个数组中线性排列，因此缓存性能会更好。我将这些与内置的qsort进行了比较，其中包括将碎片列表中的所有内容复制到数组中并再次复制结果。每个算法在相同的10个数据集上运行，并对结果进行平均。
这些是结果：
N = 1000：
具有合并排序的碎片列表：0.000000秒
数组使用qsort：0.000000秒
带有合并排序的打包列表：0.000000秒
N = 100000：
具有合并排序的碎片列表：0.039000秒
带qsort的数组：0.025000秒
合并排序的打包列表：0.009000秒
N = 1000000：
具有合并排序的碎片列表：1.162000秒
带qsort的数组：0.420000秒
带有合并排序的打包列表：0.112000秒
N = 100000000：
具有合并排序的碎片列表：364.797000秒
带qsort的数组：61.166000秒
合并排序的打包列表：16.525000秒
结论：
至少在我的机器上，复制到数组是非常值得的，以提高缓存性能，因为在现实生活中很少有完整的链接列表。应该注意的是我的机器有2.8GHz的Phenom II，但只有0.6GHz的RAM，所以缓存非常重要。
比较排序（即基于比较元素的排序）不可能比n log n更快。底层数据结构是什么并不重要。见Wikipedia。
利用列表中存在大量相同元素（例如计数排序）或列表中元素的某些预期分布的其他类型的排序更快，但我无法想到任何特别好的工作在链表上。
如上所述，基于比较的一般数据排序的下限将是O（n log n）。简要地重新阐述这些论点，有n！列表可以排序的不同方式。任何一种有n的比较树！ （这是在O（n ^ n））可能的最终排序将至少需要log（n！）作为其高度：这给你一个O（log（n ^ n））下界，即O（n记录n）。
因此，对于链表上的一般数据，对可以比较两个对象的任何数据起作用的最佳排序将是O（n log n）。但是，如果您有一个更有限的工作领域，您可以缩短所需的时间（至少与n成比例）。例如，如果您使用的是不大于某个值的整数，则可以使用Counting Sort或Radix Sort，因为它们使用您要排序的特定对象来降低与n成比例的复杂性。但要小心，这些会增加一些您可能不会考虑的复杂性（例如，Counting Sort和Radix排序都会添加基于您要排序的数字大小的因子，O（n + k） ）其中k是Counting Sort的最大数量的大小，例如）。
此外，如果您碰巧拥有具有完美哈希的对象（或者至少是以不同方式映射所有值的哈希），您可以尝试对其哈希函数使用计数或基数排序。
这是关于这个主题的一篇很好的小论文。他的实证结论是Treesort是最好的，其次是Quicksort和Mergesort。沉积物排序，冒泡排序，选择排序表现非常糟糕。
Ching-Kuang Shene的链接列表排序算法比较研究
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981
Radix sort特别适合链表，因为很容易制作一个与每个可能的数字值对应的头指针表。
合并排序不需要O（1）访问，并且是O（n ln n）。没有用于排序一般数据的已知算法优于O（n ln n）。
特殊数据算法，例如基数排序（限制数据大小）或直方图排序（计算离散数据）可以对具有较低增长函数的链表进行排序，只要您使用具有O（1）访问权限的不同结构作为临时存储。
另一类特殊数据是几乎排序的列表的比较类型，其中k个元素不按顺序排列。这可以在O（kn）操作中排序。
将列表复制到数组并返回将是O（N），因此如果空间不是问题，则可以使用任何排序算法。
例如，给定包含uint_8的链表，此代码将使用直方图排序在O（N）时间内对其进行排序：
#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
typedef struct _list list_t;
struct _list {
uint8_t value;
list_t *next;
};
list_t* sort_list ( list_t* list )
{
list_t* heads[257] = {0};
list_t* tails[257] = {0};
// O(N) loop
for ( list_t* it = list; it != 0; it = it -> next ) {
list_t* next = it -> next;
if ( heads[ it -> value ] == 0 ) {
heads[ it -> value ] = it;
} else {
tails[ it -> value ] -> next = it;
}
tails[ it -> value ] = it;
}
list_t* result = 0;
// constant time loop
for ( size_t i = 255; i-- > 0; ) {
if ( tails[i] ) {
tails[i] -> next = result;
result = heads[i];
}
}
return result;
}
list_t* make_list ( char* string )
{
list_t head;
for ( list_t* it = &head; *string; it = it -> next, ++string ) {
it -> next = malloc ( sizeof ( list_t ) );
it -> next -> value = ( uint8_t ) * string;
it -> next -> next = 0;
}
return head.next;
}
void free_list ( list_t* list )
{
for ( list_t* it = list; it != 0; ) {
list_t* next = it -> next;
free ( it );
it = next;
}
}
void print_list ( list_t* list )
{
printf ( "[ " );
if ( list ) {
printf ( "%c", list -> value );
for ( list_t* it = list -> next; it != 0; it = it -> next )
printf ( ", %c", it -> value );
}
printf ( " ]\n" );
}
int main ( int nargs, char** args )
{
list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" );
print_list ( list );
list_t* sorted = sort_list ( list );
print_list ( sorted );
free_list ( list );
}
不是您的问题的直接答案，但如果您使用Skip List，它已经排序并具有O（log N）搜索时间。
据我所知，最好的排序算法是O（n * log n），无论容器是什么 - 它已被证明广义上的排序（mergesort / quicksort等样式）不能降低。使用链接列表不会给您更好的运行时间。
在O（n）中运行的唯一算法是“hack”算法，其依赖于计数值而不是实际排序。