# 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] 用于对非原始类型的数组排序。

## 参考文献

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.
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. ^ 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.
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） （美国英语）.