Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Timsort

Sorting Algorithm

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, particularly data that already contains ordered runs. It was implemented by Tim Peters in 2002 for use in the Python programming language, and variants of it have since been adopted as the default sort in Java and Android, among other platforms. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Time Complexity
Time Complexity (category)
Linear Time -- O(n) 1
Time Complexity (category)
Linearithmic Time -- O(n log n) 1
Time Complexity
Worst-case and average O(n log n); best case O(n) on already-sorted input. 1
Credited To
Tim Peters, 2002. 1
Connections

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Timsort
Sources
1. Wikipedia: Timsort
Wikimedia Foundation
  • Lead section
    It was implemented by Tim Peters in 2002 for use in the Python programming language.
  • Wikipedia Timsort infobox time O(n log n)
  • In Field: Algorithms and Complexity Theory, Lead sentence
    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.
  • In Group: Comparison Sorting Algorithms, Lead
    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.
View the Source
Wikidata: Timsort
Wikidata Q942403, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.