复杂的排序方法

如果我有一些排序列表，说，使用Python中sort method如下面..复杂的排序方法

a=[3,7,1,0,2,8] 
a.sort() 
print a

什么分拣的情况下是这样计划的worst, average and best cases？他们每个人有什么复杂性？ Python使用什么排序技术？

2014-09-12 h8pathak

另请参阅[关于内置排序Python的（）方法（http://stackoverflow.com/q/1517347）和[Python的内部排序方法（HTTP：// stackoverflow.com/q/21558903） – 2014-09-12 17:38:16

这个问题更具体。 – h8pathak 2014-09-12 17:50:14

不是真的;方法和复杂性都在特定副本中命名，您可以从提供的链接中获得更多信息。 – 2014-09-12 18:18:02

Python使用Timsort，它是以发明它的Python开发人员Tim Peters的名字命名的。维基百科页面有复杂的信息：

Worst case performance O(nlogn) 
Best case performance O(n) 
Average case performance O(nlogn) 
Worst case space complexity O(n)

2014-09-12 17:35:57 asmeurer

Cpython（可能还有其他实现）使用Timsort - 语言参考中的唯一要求是排序方法是稳定的。我想可能有一两个实现可能会使用'mergesort'，除了最好的情况下，这个复杂度几乎相同。 – mgilson 2014-09-12 17:38:07

源代码树中有一个[document]（http://hg.python.org/cpython/file/default/Objects/listsort.txt），它描述了timsort如何工作和详细执行。 – uranusjr 2014-09-12 17:40:01

内置排序函数背后的C代码。 http://svn.python.org/view/python/trunk/Objects/listobject.c?revision=69227&view=markup – h8pathak 2014-09-12 17:48:03

回答