Python排序方法的复杂性

Question

如果我必须对某些列表进行排序,比如说,使用sort methodPython中的如下所示.

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

worst, average and best cases在排序的情况下,这些程序有哪些？他们每个人都有什么复杂性？python在这里使用什么排序技术？

Answer 1

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)