Timsort
Sign in to saveTimsort 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 until it was replaced in 3.11 by Powersort, a derived algorithm with a more robust merge policy. Timso
Key facts
- Algorithm.class
- Sorting algorithm
- Algorithm.caption
- A visual representation of Timsort
- Algorithm.data
- Array
- Algorithm.time
- O(n\log n)
- Algorithm.best time
- O(n)
- Algorithm.average time
- O(n\log n)
- Algorithm.space
- O(n)
- Algorithm.optimal
- No; Powersort and Peeksort are closer to optimal
via Wikipedia infobox
Article
15 sectionsContents
- Operation
- Merge criteria
- Merge space overhead
- Merge direction
- Galloping mode during merge
- Descending runs
- Minimum run size
- Algorithm
- Analysis
- Adoption and influence
- Influence
- Formal verification
- References
- Further reading
- External links
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 until it was replaced in 3.11 by Powersort, a derived algorithm with a more robust merge policy. Timsort is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, on V8, and in Swift. Rust used a custom version of Timsort until May 2024.
The galloping technique derives from Carlsson, Levcopoulos, and O. Petersson's 1990 paper "Sublinear merging and natural merge sort" and Peter McIlroy's 1993 paper "Optimistic Sorting and Information Theoretic Complexity".