Timsort

Timsort 是一種混合穩定的排序算法，源自合併排序和插入排序，旨在較好地處理真實世界中各種各樣的數據。它使用了 Peter Mcllroy 的"樂觀排序和信息理論上複雜性"中的技術，參見 第四屆年度ACM-SIAM離散算法研討會論文集，第467-474頁，1993年。 它由 Tim Peters 在2002年實現，並應用於 Python程式語言。該算法通過查找已經排好序的數據子序列，在此基礎上對剩餘部分更有效地排序。 該算法通過不斷地將特定子序列（稱為一個 run ）與現有的 run 合併，直到滿足某些條件為止來達成的更有效的排序。 從 2.3 版本起，Timsort 一直是 Python 的標準排序算法。 它還被 Java SE7^[4], Android platform^[5], GNU Octave,^[6] 谷歌瀏覽器,^[7] 和 Swift^[8] 用於對非原始類型的數組排序。

Timsort
概況
類別	排序算法
資料結構	數組
複雜度
平均時間複雜度	${\displaystyle O(n\log n)}$
最壞時間複雜度	${\displaystyle O(n\log n)}$[1][2]
最優時間複雜度	${\displaystyle O(n)}$[3]
空間複雜度	${\displaystyle O(n)}$
相關變量的定義