Timsort

<p>Timsort is a <a href="/facts/Hybrid_algorithm/mgL7jc0c">hybrid</a>, stable <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting algorithm</a>, derived from <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a> and <a href="/facts/Insertion_sort/N5yWe8Co">insertion sort</a>, designed to perform well on many kinds of real-world data. It was implemented by <a href="/facts/Tim_Peters_(software_engineer)/HdpImU97">Tim Peters</a> in 2002 for use in the <a href="/facts/Python_(programming_language)/YbuGqofa">Python programming language</a>. 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 has been Python's standard sorting algorithm since version 2.3, but starting with 3.11 it uses Powersort instead, a derived algorithm with a more robust merge policy. Timsort is also used to sort arrays of non-primitive type in <a href="/facts/Java_7/Br6eHSP8">Java SE 7</a>, on the <a href="/facts/Android_(operating_system)/nNyHb0xz">Android platform</a>, in <a href="/facts/GNU_Octave/vVVq5evM">GNU Octave</a>, on <a href="/facts/V8_(JavaScript_engine)/0Fd3taMh">V8</a>, in <a href="/facts/Swift_(programming_language)/A7qHQC32">Swift</a>, and <a href="/facts/Rust_(programming_language)/8JNMV19F">Rust</a>.
</p><p>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".
</p>

Timsort open-in-new

Timsort