python - sort（）関数の複雑さは何ですか？

Question

私はリストのリストを持っており、以下を使用してそれらを並べ替えています

data=sorted(data, key=itemgetter(0))

このPython関数の実行時の複雑さは何ですか？

Answer 1

と一緒に使用すると、平均と最悪の場合の両方でソートがitemgetter(0)提供されます。O(1)dataO(n log n)

Pythonで使用される並べ替え方法の詳細については、ウィキペディアを参照してください。

Answer 2

並べ替えは並べ替えに似ていますが、最初の並べ替えが反復可能ファイルから新しい並べ替えリストを作成し、並べ替えが適切に並べ替えられる点が異なります。主な違いは、スペースの複雑さです。

Answer 3

それはティムソートであり、ティムソートはマージソートと挿入ソートに基づく一種の適応ソートアルゴリズムであり、比較ソートに属すると思いました。比較ソートでは、lg（N！ ）〜NlogN。