Global InformationTimsort information
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | [1][2] |
| Best-case performance | [3] |
| Average performance | |
| Worst-case space complexity | |
| Optimal | No[4] |
Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort was Python's standard sorting algorithm from version 2.3 to version 3.10,[5] and is used to sort arrays of non-primitive type in Java SE 7,[6] on the Android platform,[7] in GNU Octave,[8] on V8,[9] Swift,[10] and inspired the sorting algorithm used in Rust.[11]
It uses techniques from Peter McIlroy's 1993 paper "Optimistic Sorting and Information Theoretic Complexity".[12]
- ^ Peters, Tim (20 July 2002). "[Python-Dev] Sorting". Python Developers Mailinglist. Retrieved 24 February 2011.
[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).
- ^ Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). [DROPS]. doi:10.4230/LIPIcs.ESA.2018.4. ISBN 9783959770811. S2CID 44091254. Retrieved 1 September 2018.
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 (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
- ^ Munro, J. Ian; Wild, Sebastian (2018). Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. p. 12. arXiv:1805.04154. doi:10.4230/lipics.esa.2018.63. S2CID 21678081.
- ^ James, Mike (21 December 2022). "Python Now Uses Powersort". www.i-programmer.info. Retrieved 24 January 2024.
- ^ "[#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort". JDK Bug System. Retrieved 11 June 2014.
- ^ "Class: java.util.TimSort<T>". Android Gingerbread Documentation. Archived from the original on 16 July 2015. Retrieved 24 February 2011.
- ^
"liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 February 2013.
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. Retrieved 21 December 2018.
- ^ "Is sort() stable in Swift 5?". Swift Forums. 4 July 2019. Retrieved 4 July 2019.
- ^ "slice - Rust". doc.rust-lang.org. Retrieved 8 December 2022.
The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.
- ^ McIlroy, Peter (January 1993). "Optimistic Sorting and Information Theoretic Complexity". Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 467–474. ISBN 0-89871-313-7.