{"id":6745,"date":"2020-12-23T10:20:58","date_gmt":"2020-12-23T04:50:58","guid":{"rendered":"http:\/\/www.pythonpool.com\/?p=6745"},"modified":"2021-08-06T08:01:57","modified_gmt":"2021-08-06T02:31:57","slug":"python-timsort","status":"publish","type":"post","link":"https:\/\/www.pythonpool.com\/python-timsort\/","title":{"rendered":"TimSort: Algorithm and Implementation in Python"},"content":{"rendered":"\n<p>Hello coders!! In this article, we will learn about the TimSort algorithm and learn its implementation in Python. <strong>Tim Peters created TimSort in the year 2002 t<\/strong>o improve the sorting performance of the list.  <strong>sort()<\/strong> function makes use of this algorithm and is the fastest sorting algorithm.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_74 counter-hierarchy ez-toc-counter ez-toc-transparent ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #990303;color:#990303\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #990303;color:#990303\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 eztoc-toggle-hide-by-default' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#What_is_Python_TimSort_Algorithm\" >What is Python TimSort Algorithm?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Python_TimSort_Algorithm\" >Python TimSort Algorithm:<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Understanding_the_algorithm_in_detail\" >Understanding the algorithm in detail:<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Implementation_of_Tims_Algorithm_in_Python\" >Implementation of Tim&#8217;s Algorithm in Python:<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Output\" >Output:<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Complexity_Analysis_of_Python_TimSort_Algorithm\" >Complexity Analysis of Python TimSort Algorithm:<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Advantages_of_Python_Timsort\" >Advantages of Python Timsort:<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Must_Read\" >Must Read<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#Conclusion\" >Conclusion:<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\" id=\"h-what-is-python-timsort-algorithm\"><span class=\"ez-toc-section\" id=\"What_is_Python_TimSort_Algorithm\"><\/span>What is Python TimSort Algorithm?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p> TimSort is a sorting algorithm that is a<strong> hybrid of merge sort and insertion sort algorithm<\/strong>. It is a stable algorithm and works on real-time data. In this, the list that needs to be sorted is first analyzed, and based on that the best approach is selected. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-python-timsort-algorithm\"><span class=\"ez-toc-section\" id=\"Python_TimSort_Algorithm\"><\/span>Python TimSort Algorithm:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Divide the array into blocks known as run<\/li><li>The size of a run can either be 32 or 64<\/li><li>Sort the elements of every run using insertion sort<\/li><li>Merge the sorted runs using the merge sort algorithm<\/li><li> Double the size of the merged array after every iteration<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-understanding-the-algorithm-in-detail\"><span class=\"ez-toc-section\" id=\"Understanding_the_algorithm_in_detail\"><\/span>Understanding the algorithm in detail:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-calculation-of-minrun\">Calculation of minrun:<\/h3>\n\n\n\n<p>We know now that the first step of the Python Timsort algorithm is to divide the blocks into runs. <strong>minrun<\/strong> is the minimum length of each run. It is calculated from the number of elements of the array N.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>It should not be very long as we will implement insertion sort to sort each run and we know that insertion sort works more efficiently for shorter arrays<\/li><li>However, it should also not be too short as the next step is to merge these runs, shorter runs will result in more number of runs<\/li><li>It is beneficial if N\/minrun is a <a href=\"http:\/\/www.pythonpool.com\/numpy-power\/\" target=\"_blank\" rel=\"noreferrer noopener\">power<\/a> of 2 as it will result in the best performance by merge sort.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-splitting-and-sorting-of-runs\">Splitting and sorting of runs:<\/h3>\n\n\n\n<p>When we reach this step, we already have two values &#8211; N and minrun<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A&nbsp;<strong>descending flag<\/strong>&nbsp;is by the comparison between the first 2 items, if there is only 1 item left, then it is set as&nbsp;<code>false<\/code>.<\/li><li>Then the other elements are iterated and checked whether they are still in ascending or &#8220;strict&#8221; descending order until an item that does not follow this order is found.<\/li><li>After this, we will have a run in either ascending or &#8220;strict&#8221; descending order. If it is in a &#8220;strict&#8221; descending order we need to reverse it.<\/li><li>Then we check to make sure that the length of the run satisfies minrun. If it is smaller, we compensate for the following items to make it achieve the minrun size.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-merging-of-runs\">merging of runs:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>At first, we will create a temporary run having the size of the smallest of the merged runs.<\/li><li>After this, we need to copy the shortest <a href=\"https:\/\/en.wikipedia.org\/wiki\/Run_command\" target=\"_blank\" rel=\"noreferrer noopener\">run<\/a> into the temporary one.<\/li><li>Now, we will mark the first element of the large and temporary array is as the current position.<\/li><li>In each following step, we will compare the elements in the large and temporary arrays, and the smaller ones will be moved into a new sorted array. <\/li><li>We need to repeat the above step until one of the arrays runs out.<\/li><li>Lastly, we will add All the remaining elements to the end of the new one.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-implementation-of-tim-s-algorithm-in-python\"><span class=\"ez-toc-section\" id=\"Implementation_of_Tims_Algorithm_in_Python\"><\/span>Implementation of Tim&#8217;s Algorithm in Python:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nMINIMUM= 32\n \ndef find_minrun(n): \n \n    r = 0\n    while n &gt;= MINIMUM: \n        r |= n &amp; 1\n        n &gt;&gt;= 1\n    return n + r \n \ndef insertion_sort(array, left, right): \n    for i in range(left+1,right+1):\n        element = array&#x5B;i]\n        j = i-1\n        while element&lt;array&#x5B;j] and j&gt;=left :\n            array&#x5B;j+1] = array&#x5B;j]\n            j -= 1\n        array&#x5B;j+1] = element\n    return array\n             \ndef merge(array, l, m, r): \n \n    array_length1= m - l + 1\n    array_length2 = r - m \n    left = &#x5B;]\n    right = &#x5B;]\n    for i in range(0, array_length1): \n        left.append(array&#x5B;l + i]) \n    for i in range(0, array_length2): \n        right.append(array&#x5B;m + 1 + i]) \n \n    i=0\n    j=0\n    k=l\n  \n    while j &lt; array_length2 and  i &lt; array_length1: \n        if left&#x5B;i] &lt;= right&#x5B;j]: \n            array&#x5B;k] = left&#x5B;i] \n            i += 1\n \n        else: \n            array&#x5B;k] = right&#x5B;j] \n            j += 1\n \n        k += 1\n \n    while i &lt; array_length1: \n        array&#x5B;k] = left&#x5B;i] \n        k += 1\n        i += 1\n \n    while j &lt; array_length2: \n        array&#x5B;k] = right&#x5B;j] \n        k += 1\n        j += 1\n \ndef tim_sort(array): \n    n = len(array) \n    minrun = find_minrun(n) \n \n    for start in range(0, n, minrun): \n        end = min(start + minrun - 1, n - 1) \n        insertion_sort(array, start, end) \n  \n    size = minrun \n    while size &lt; n: \n \n        for left in range(0, n, 2 * size): \n \n            mid = min(n - 1, left + size - 1) \n            right = min((left + 2 * size - 1), (n - 1)) \n            merge(array, left, mid, right) \n \n        size = 2 * size \n \n \n \n \narray = &#x5B;-1,5,0,-3,11,9,-2,7,0] \n \nprint(&quot;Array:&quot;) \nprint(array) \n \ntim_sort(array) \n \nprint(&quot;Sorted Array:&quot;) \nprint(array)\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"h-output\"><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<div class=\"wp-block-image is-style-default\"><figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"367\" height=\"187\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/image-121.png\" alt=\"Output for timsort algorithm obtained by executing the given code\" class=\"wp-image-6749\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/image-121.png 367w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/image-121-300x153.png 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/image-121-150x76.png 150w\" sizes=\"(max-width: 367px) 100vw, 367px\" \/><figcaption><strong><em>OUTPUT<\/em><\/strong><\/figcaption><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-complexity-analysis-of-python-timsort-algorithm\"><span class=\"ez-toc-section\" id=\"Complexity_Analysis_of_Python_TimSort_Algorithm\"><\/span>Complexity Analysis of Python TimSort Algorithm:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>Worst-case time complexity: O(n log n)<\/li><li>Best-case time complexity: O(n)<\/li><li>Average-case time complexity: O(n log n)<\/li><li>Worst-case space complexity: O(n)<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-advantages-of-python-timsort\"><span class=\"ez-toc-section\" id=\"Advantages_of_Python_Timsort\"><\/span>Advantages of Python Timsort:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>It is a stable sorting algorithm<\/li><li>Works for real-time data<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-must-read\"><span class=\"ez-toc-section\" id=\"Must_Read\"><\/span>Must Read<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"http:\/\/www.pythonpool.com\/insertion-sort-python\/\" rel=\"noreferrer noopener\" target=\"_blank\">Insertion Sort in Python [Program, Algorithm, Example]<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/shell-sort-python\/\" rel=\"noreferrer noopener\" target=\"_blank\">Shell Sort Algorithm and Program in Python<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/python-sort-list-of-lists\/\" rel=\"noreferrer noopener\" target=\"_blank\">Learning Various Ways in Python to Sort the List of Lists<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/sorting-techniques-using-python\/\" rel=\"noreferrer noopener\" target=\"_blank\">Sorting Techniques Using Python<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/python-sort-list-of-tuples\/\" rel=\"noreferrer noopener\" target=\"_blank\">HOW TO PYTHON SORT LIST OF TUPLES<\/a><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-conclusion\"><span class=\"ez-toc-section\" id=\"Conclusion\"><\/span>Conclusion:<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>That is all about the Python TimSort algorithm. The<strong> in-built sort() function of Python uses this algorithm as it provides a stable sorting approach<\/strong>. It is faster than other sorting algorithms and can be directly implemented in python using the sort() method.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello coders!! In this article, we will learn about the TimSort algorithm and learn its implementation in Python. Tim Peters created TimSort in the year &#8230; <\/p>\n<p class=\"read-more-container\"><a title=\"TimSort: Algorithm and Implementation in Python\" class=\"read-more button\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/#more-6745\" aria-label=\"More on TimSort: Algorithm and Implementation in Python\">Read more<\/a><\/p>\n","protected":false},"author":12,"featured_media":6812,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1654],"tags":[2953,2954,2955,2949,2952,2956,2950,2951],"class_list":["post-6745","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","tag-python-how-to-use-timsort","tag-python-timsort","tag-python-timsort-bug","tag-python-timsort-example","tag-timsort-code-python","tag-timsort-in-python-performance","tag-timsort-python","tag-timsort-python-code","infinite-scroll-item"],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v20.1 (Yoast SEO v25.0) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>TimSort: Algorithm and Implementation in Python - Python Pool<\/title>\n<meta name=\"description\" content=\"Python TimSort is a hybrid sorting algorithm of merge sort and insertion sort algorithm. It is a stable algorithm, works on real-time data.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.pythonpool.com\/python-timsort\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"TimSort: Algorithm and Implementation in Python\" \/>\n<meta property=\"og:description\" content=\"Hello coders!! In this article, we will learn about the TimSort algorithm and learn its implementation in Python. Tim Peters created TimSort in the year\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.pythonpool.com\/python-timsort\/\" \/>\n<meta property=\"og:site_name\" content=\"Python Pool\" \/>\n<meta property=\"article:published_time\" content=\"2020-12-23T04:50:58+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-08-06T02:31:57+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1350\" \/>\n\t<meta property=\"og:image:height\" content=\"650\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Prachee Sao\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@pythonpool\" \/>\n<meta name=\"twitter:site\" content=\"@pythonpool\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prachee Sao\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/\"},\"author\":{\"name\":\"Prachee Sao\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/person\/b91d749826b21e606d55cda77d51ef47\"},\"headline\":\"TimSort: Algorithm and Implementation in Python\",\"datePublished\":\"2020-12-23T04:50:58+00:00\",\"dateModified\":\"2021-08-06T02:31:57+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/\"},\"wordCount\":646,\"commentCount\":4,\"publisher\":{\"@id\":\"https:\/\/www.pythonpool.com\/#organization\"},\"image\":{\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png\",\"keywords\":[\"python how to use timsort\",\"python timsort\",\"python timsort bug\",\"python timsort example\",\"timsort code python\",\"timsort in python performance\",\"timsort python\",\"timsort python code\"],\"articleSection\":[\"Algorithm\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/www.pythonpool.com\/python-timsort\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/\",\"url\":\"https:\/\/www.pythonpool.com\/python-timsort\/\",\"name\":\"TimSort: Algorithm and Implementation in Python - Python Pool\",\"isPartOf\":{\"@id\":\"https:\/\/www.pythonpool.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png\",\"datePublished\":\"2020-12-23T04:50:58+00:00\",\"dateModified\":\"2021-08-06T02:31:57+00:00\",\"description\":\"Python TimSort is a hybrid sorting algorithm of merge sort and insertion sort algorithm. It is a stable algorithm, works on real-time data.\",\"breadcrumb\":{\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.pythonpool.com\/python-timsort\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage\",\"url\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png\",\"contentUrl\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png\",\"width\":1350,\"height\":650,\"caption\":\"timsort python\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.pythonpool.com\/python-timsort\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.pythonpool.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"TimSort: Algorithm and Implementation in Python\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.pythonpool.com\/#website\",\"url\":\"https:\/\/www.pythonpool.com\/\",\"name\":\"Python Pool\",\"description\":\"Your One-Stop Python Learning Destination\",\"publisher\":{\"@id\":\"https:\/\/www.pythonpool.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.pythonpool.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.pythonpool.com\/#organization\",\"name\":\"Python Pool\",\"url\":\"https:\/\/www.pythonpool.com\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/\",\"url\":\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png\",\"contentUrl\":\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png\",\"width\":452,\"height\":185,\"caption\":\"Python Pool\"},\"image\":{\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/pythonpool\",\"https:\/\/www.youtube.com\/c\/pythonpool\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/person\/b91d749826b21e606d55cda77d51ef47\",\"name\":\"Prachee Sao\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/d018c3758049ab2511d0772ac1f73c338aaa8c921577f39e0f1e5716fc7efcb4?s=96&d=wavatar&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/d018c3758049ab2511d0772ac1f73c338aaa8c921577f39e0f1e5716fc7efcb4?s=96&d=wavatar&r=g\",\"caption\":\"Prachee Sao\"}}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"TimSort: Algorithm and Implementation in Python - Python Pool","description":"Python TimSort is a hybrid sorting algorithm of merge sort and insertion sort algorithm. It is a stable algorithm, works on real-time data.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.pythonpool.com\/python-timsort\/","og_locale":"en_US","og_type":"article","og_title":"TimSort: Algorithm and Implementation in Python","og_description":"Hello coders!! In this article, we will learn about the TimSort algorithm and learn its implementation in Python. Tim Peters created TimSort in the year","og_url":"https:\/\/www.pythonpool.com\/python-timsort\/","og_site_name":"Python Pool","article_published_time":"2020-12-23T04:50:58+00:00","article_modified_time":"2021-08-06T02:31:57+00:00","og_image":[{"width":1350,"height":650,"url":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png","type":"image\/png"}],"author":"Prachee Sao","twitter_card":"summary_large_image","twitter_creator":"@pythonpool","twitter_site":"@pythonpool","twitter_misc":{"Written by":"Prachee Sao","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.pythonpool.com\/python-timsort\/#article","isPartOf":{"@id":"https:\/\/www.pythonpool.com\/python-timsort\/"},"author":{"name":"Prachee Sao","@id":"https:\/\/www.pythonpool.com\/#\/schema\/person\/b91d749826b21e606d55cda77d51ef47"},"headline":"TimSort: Algorithm and Implementation in Python","datePublished":"2020-12-23T04:50:58+00:00","dateModified":"2021-08-06T02:31:57+00:00","mainEntityOfPage":{"@id":"https:\/\/www.pythonpool.com\/python-timsort\/"},"wordCount":646,"commentCount":4,"publisher":{"@id":"https:\/\/www.pythonpool.com\/#organization"},"image":{"@id":"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage"},"thumbnailUrl":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png","keywords":["python how to use timsort","python timsort","python timsort bug","python timsort example","timsort code python","timsort in python performance","timsort python","timsort python code"],"articleSection":["Algorithm"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.pythonpool.com\/python-timsort\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.pythonpool.com\/python-timsort\/","url":"https:\/\/www.pythonpool.com\/python-timsort\/","name":"TimSort: Algorithm and Implementation in Python - Python Pool","isPartOf":{"@id":"https:\/\/www.pythonpool.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage"},"image":{"@id":"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage"},"thumbnailUrl":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png","datePublished":"2020-12-23T04:50:58+00:00","dateModified":"2021-08-06T02:31:57+00:00","description":"Python TimSort is a hybrid sorting algorithm of merge sort and insertion sort algorithm. It is a stable algorithm, works on real-time data.","breadcrumb":{"@id":"https:\/\/www.pythonpool.com\/python-timsort\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.pythonpool.com\/python-timsort\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonpool.com\/python-timsort\/#primaryimage","url":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png","contentUrl":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/12\/Theatre-Actor-Portfolio-Website-42.png","width":1350,"height":650,"caption":"timsort python"},{"@type":"BreadcrumbList","@id":"https:\/\/www.pythonpool.com\/python-timsort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.pythonpool.com\/"},{"@type":"ListItem","position":2,"name":"TimSort: Algorithm and Implementation in Python"}]},{"@type":"WebSite","@id":"https:\/\/www.pythonpool.com\/#website","url":"https:\/\/www.pythonpool.com\/","name":"Python Pool","description":"Your One-Stop Python Learning Destination","publisher":{"@id":"https:\/\/www.pythonpool.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.pythonpool.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.pythonpool.com\/#organization","name":"Python Pool","url":"https:\/\/www.pythonpool.com\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/","url":"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png","contentUrl":"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png","width":452,"height":185,"caption":"Python Pool"},"image":{"@id":"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/pythonpool","https:\/\/www.youtube.com\/c\/pythonpool"]},{"@type":"Person","@id":"https:\/\/www.pythonpool.com\/#\/schema\/person\/b91d749826b21e606d55cda77d51ef47","name":"Prachee Sao","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonpool.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/d018c3758049ab2511d0772ac1f73c338aaa8c921577f39e0f1e5716fc7efcb4?s=96&d=wavatar&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/d018c3758049ab2511d0772ac1f73c338aaa8c921577f39e0f1e5716fc7efcb4?s=96&d=wavatar&r=g","caption":"Prachee Sao"}}]}},"_links":{"self":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts\/6745","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/comments?post=6745"}],"version-history":[{"count":16,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts\/6745\/revisions"}],"predecessor-version":[{"id":15201,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts\/6745\/revisions\/15201"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/media\/6812"}],"wp:attachment":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/media?parent=6745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/categories?post=6745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/tags?post=6745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}