排序列表上的Python排序复杂性

Question

Python 中的sort(already_sorted_list) 复杂度是多少？ Python 是否检查给定的 iterable 是否已排序，还是我必须自己做？我在文档中的任何地方都找不到它。

Answer 1

这完全依赖于实现。 python 所保证的只是内置排序算法是稳定的(比较相等的元素保留它们的相对顺序)。如果一个实现想要......，它甚至可以使用稳定的冒泡排序。

Cpython 使用 TimSort (插入排序和合并排序的混合体)如果输入已经排序，我认为它具有 O(N) 复杂度——它获得了插入排序的最佳情况性能和合并排序的最坏情况性能 (O(NlogN))。

如果您对实现感到好奇，source code有一个非常好的描述。