Python排序方法的复杂性

Question

如果我想对一个列表，比如说a，进行排序，可以使用Python中的sort方法，像下面这样..

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

那么在排序的情况下，这种程序的最坏情况、平均情况和最好情况分别是什么呢？每种情况的复杂度又是什么？Python使用了什么排序技术呢？

Answer 1

Python使用了一种叫做的排序算法，这个名字是为了纪念发明它的Python开发者Tim Peters。你可以在维基百科上找到关于它的复杂度信息：

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