Timsort

Timsort
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] 用於對非原始類型的數組排序。

參考文獻

^ Peters, Tim. [Python-Dev] Sorting. Python Developers Mailinglist. [24 February 2011]. （原始內容存檔於2018-07-17）. [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).
^ [DROPS]. [1 September 2018]. （原始內容存檔於2019-09-19）. TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.
^ Chandramouli, Badrish; Goldstein, Jonathan. Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS. 2014.
^ [#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort. JDK Bug System. [11 June 2014]. （原始內容存檔於2020-01-11）.
^ Class: java.util.TimSort<T>. Android Gingerbread Documentation. [24 February 2011]. （原始內容存檔於2015-07-16）.
^ liboctave/util/oct-sort.cc. Mercurial repository of Octave source code. [18 February 2013]. （原始內容存檔於2019-02-06）. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.
^ Getting things sorted in V8 · V8. v8.dev. [2018-12-21]. （原始內容存檔於2018-12-21）.
^ Is sort() stable in Swift 5?. Swift Forums. 2019-07-04 [2019-07-04]. （原始內容存檔於2019-07-04）（美國英語）.

外部連結

[1] Peters, Tim. [Python-Dev] Sorting. Python Developers Mailinglist. [24 February 2011]. （原始內容存檔於2018-07-17）. [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).

[2] [DROPS]. [1 September 2018]. （原始內容存檔於2019-09-19）. TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.

[Chandramouli-3] Chandramouli, Badrish; Goldstein, Jonathan. Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS. 2014.

[4] [#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort. JDK Bug System. [11 June 2014]. （原始內容存檔於2020-01-11）.

[5] Class: java.util.TimSort<T>. Android Gingerbread Documentation. [24 February 2011]. （原始內容存檔於2015-07-16）.

[6] tave/util/oct-sort.cc. Mercurial repository of Octave source code. [18 February 2013]. （原始內容存檔於2019-02-06）. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.

[7] Getting things sorted in V8 · V8. v8.dev. [2018-12-21]. （原始內容存檔於2018-12-21）.

[8] Is sort() stable in Swift 5?. Swift Forums. 2019-07-04 [2019-07-04]. （原始內容存檔於2019-07-04）（美國英語）.

[4]

[5]

[6]

[7]

[8]

[1]

[2]

[3]