Python集合排序，为什么这么快？

Question

为什么Python内置的sorted在集合上运行得这么快呢？

我说的是真的很快，我用它处理了一个有80000条数据的集合，结果耗时非常短（time.clock()的输出差值是0.0）。这是不是有什么优化的原因呢？

集合里的记录是已经排好序的吗？

顺便问一下，集合的排序是怎么实现的？能给我看看代码吗？

Answer 1

这里没有什么特别的魔法：排序是用C语言高效实现的。time.clock并不是测试Python代码的最佳方法，因为在某些平台上，它的输出精度可能比较低。为了得到更好的结果，建议使用timeit模块来测量经过的时间。

排序集合也没有什么特别的算法。当你在一个set（或者其他任何东西）上调用内置的sorted时，其实是做了以下事情：

def sorted(iterable):
    templist = list(iterable)
    templist.sort()
    return templist

所以，真正的“魔法”在于这个list.sort方法。（具体的实现细节可以在旁边的文件中找到。)