複雜的排序方法

如果我有一些排序列表，說，使用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

回答