# TimSort

• Difficulty Level : Medium
• Last Updated : 19 Jul, 2022

TimSort is a sorting algorithm based on Insertion Sort and Merge Sort.

1. Used in Java’s Arrays.sort() as well as Python’s sorted() and sort().
2. First sort small pieces using Insertion Sort, then merges the pieces using a merge of merge sort.

We divide the Array into blocks known as Run. We sort those runs using insertion sort one by one and then merge those runs using the combine function used in merge sort. If the size of the Array is less than run, then Array gets sorted just by using Insertion Sort. The size of the run may vary from 32 to 64 depending upon the size of the array. Note that the merge function performs well when size subarrays are powers of 2. The idea is based on the fact that insertion sort performs well for small arrays.

Details of the below implementation:

• We consider the size of the run as 32 and the input array is divided into sub-array.
• We one-by-one sort pieces of size equal to run with a simple insertion sort.
• After sorting individual pieces, we merge them one by one with the merge sort. We double the size of merged subarrays after every iteration.

## C++

 `// C++ program to perform TimSort.``#include``using` `namespace` `std;``const` `int` `RUN = 32;` `// This function sorts array from left index to``// to right index which is of size atmost RUN``void` `insertionSort(``int` `arr[], ``int` `left, ``int` `right)``{``    ``for` `(``int` `i = left + 1; i <= right; i++)``    ``{``        ``int` `temp = arr[i];``        ``int` `j = i - 1;``        ``while` `(j >= left && arr[j] > temp)``        ``{``            ``arr[j+1] = arr[j];``            ``j--;``        ``}``        ``arr[j+1] = temp;``    ``}``}` `// Merge function merges the sorted runs``void` `merge(``int` `arr[], ``int` `l, ``int` `m, ``int` `r)``{``    ` `    ``// Original array is broken in two parts``    ``// left and right array``    ``int` `len1 = m - l + 1, len2 = r - m;``    ``int` `left[len1], right[len2];``    ``for` `(``int` `i = 0; i < len1; i++)``        ``left[i] = arr[l + i];``    ``for` `(``int` `i = 0; i < len2; i++)``        ``right[i] = arr[m + 1 + i];` `    ``int` `i = 0;``    ``int` `j = 0;``    ``int` `k = l;` `    ``// After comparing, we``    ``// merge those two array``    ``// in larger sub array``    ``while` `(i < len1 && j < len2)``    ``{``        ``if` `(left[i] <= right[j])``        ``{``            ``arr[k] = left[i];``            ``i++;``        ``}``        ``else``        ``{``            ``arr[k] = right[j];``            ``j++;``        ``}``        ``k++;``    ``}` `    ``// Copy remaining elements of left, if any``    ``while` `(i < len1)``    ``{``        ``arr[k] = left[i];``        ``k++;``        ``i++;``    ``}` `    ``// Copy remaining element of right, if any``    ``while` `(j < len2)``    ``{``        ``arr[k] = right[j];``        ``k++;``        ``j++;``    ``}``}` `// Iterative Timsort function to sort the``// array[0...n-1] (similar to merge sort)``void` `timSort(``int` `arr[], ``int` `n)``{``    ` `    ``// Sort individual subarrays of size RUN``    ``for` `(``int` `i = 0; i < n; i+=RUN)``        ``insertionSort(arr, i, min((i+RUN-1),``                                    ``(n-1)));` `    ``// Start merging from size RUN (or 32).``    ``// It will merge``    ``// to form size 64, then 128, 256``    ``// and so on ....``    ``for` `(``int` `size = RUN; size < n;``                             ``size = 2*size)``    ``{``        ` `        ``// pick starting point of``        ``// left sub array. We``        ``// are going to merge``        ``// arr[left..left+size-1]``        ``// and arr[left+size, left+2*size-1]``        ``// After every merge, we``        ``// increase left by 2*size``        ``for` `(``int` `left = 0; left < n;``                             ``left += 2*size)``        ``{``            ` `            ``// find ending point of``            ``// left sub array``            ``// mid+1 is starting point``            ``// of right sub array``            ``int` `mid = left + size - 1;``            ``int` `right = min((left + 2*size - 1),``                                            ``(n-1));` `            ``// merge sub array arr[left.....mid] &``            ``// arr[mid+1....right]``              ``if``(mid < right)``                ``merge(arr, left, mid, right);``        ``}``    ``}``}` `// Utility function to print the Array``void` `printArray(``int` `arr[], ``int` `n)``{``    ``for` `(``int` `i = 0; i < n; i++)``        ``printf``(``"%d  "``, arr[i]);``    ``printf``(``"\n"``);``}` `// Driver program to test above function``int` `main()``{``    ``int` `arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7,``                       ``-4, -13, 5, 8, -14, 12};``    ``int` `n = ``sizeof``(arr)/``sizeof``(arr);``    ``printf``(``"Given Array is\n"``);``    ``printArray(arr, n);` `    ``// Function Call``    ``timSort(arr, n);` `    ``printf``(``"After Sorting Array is\n"``);``    ``printArray(arr, n);``    ``return` `0;``}`

## Java

 `// Java program to perform TimSort.``class` `GFG``{` `    ``static` `int` `MIN_MERGE = ``32``;` `    ``public` `static` `int` `minRunLength(``int` `n)``    ``{``        ``assert` `n >= ``0``;``      ` `        ``// Becomes 1 if any 1 bits are shifted off``        ``int` `r = ``0``;``        ``while` `(n >= MIN_MERGE)``        ``{``            ``r |= (n & ``1``);``            ``n >>= ``1``;``        ``}``        ``return` `n + r;``    ``}` `    ``// This function sorts array from left index to``    ``// to right index which is of size atmost RUN``    ``public` `static` `void` `insertionSort(``int``[] arr, ``int` `left,``                                     ``int` `right)``    ``{``        ``for` `(``int` `i = left + ``1``; i <= right; i++)``        ``{``            ``int` `temp = arr[i];``            ``int` `j = i - ``1``;``            ``while` `(j >= left && arr[j] > temp)``            ``{``                ``arr[j + ``1``] = arr[j];``                ``j--;``            ``}``            ``arr[j + ``1``] = temp;``        ``}``    ``}` `    ``// Merge function merges the sorted runs``    ``public` `static` `void` `merge(``int``[] arr, ``int` `l,``                                 ``int` `m, ``int` `r)``    ``{``        ``// Original array is broken in two parts``        ``// left and right array``        ``int` `len1 = m - l + ``1``, len2 = r - m;``        ``int``[] left = ``new` `int``[len1];``        ``int``[] right = ``new` `int``[len2];``        ``for` `(``int` `x = ``0``; x < len1; x++)``        ``{``            ``left[x] = arr[l + x];``        ``}``        ``for` `(``int` `x = ``0``; x < len2; x++)``        ``{``            ``right[x] = arr[m + ``1` `+ x];``        ``}` `        ``int` `i = ``0``;``        ``int` `j = ``0``;``        ``int` `k = l;` `        ``// After comparing, we merge those two array``        ``// in larger sub array``        ``while` `(i < len1 && j < len2)``        ``{``            ``if` `(left[i] <= right[j])``            ``{``                ``arr[k] = left[i];``                ``i++;``            ``}``            ``else` `{``                ``arr[k] = right[j];``                ``j++;``            ``}``            ``k++;``        ``}` `        ``// Copy remaining elements``        ``// of left, if any``        ``while` `(i < len1)``        ``{``            ``arr[k] = left[i];``            ``k++;``            ``i++;``        ``}` `        ``// Copy remaining element``        ``// of right, if any``        ``while` `(j < len2)``        ``{``            ``arr[k] = right[j];``            ``k++;``            ``j++;``        ``}``    ``}` `    ``// Iterative Timsort function to sort the``    ``// array[0...n-1] (similar to merge sort)``    ``public` `static` `void` `timSort(``int``[] arr, ``int` `n)``    ``{``        ``int` `minRun = minRunLength(MIN_MERGE);``      ` `        ``// Sort individual subarrays of size RUN``        ``for` `(``int` `i = ``0``; i < n; i += minRun)``        ``{``            ``insertionSort(arr, i,``                          ``Math.min((i + MIN_MERGE - ``1``), (n - ``1``)));``        ``}` `        ``// Start merging from size``        ``// RUN (or 32). It will``        ``// merge to form size 64,``        ``// then 128, 256 and so on``        ``// ....``        ``for` `(``int` `size = minRun; size < n; size = ``2` `* size)``        ``{` `            ``// Pick starting point``            ``// of left sub array. We``            ``// are going to merge``            ``// arr[left..left+size-1]``            ``// and arr[left+size, left+2*size-1]``            ``// After every merge, we``            ``// increase left by 2*size``            ``for` `(``int` `left = ``0``; left < n;``                                 ``left += ``2` `* size)``            ``{` `                ``// Find ending point of left sub array``                ``// mid+1 is starting point of right sub``                ``// array``                ``int` `mid = left + size - ``1``;``                ``int` `right = Math.min((left + ``2` `* size - ``1``),``                                     ``(n - ``1``));` `                ``// Merge sub array arr[left.....mid] &``                ``// arr[mid+1....right]``                  ``if``(mid < right)``                    ``merge(arr, left, mid, right);``            ``}``        ``}``    ``}` `    ``// Utility function to print the Array``    ``public` `static` `void` `printArray(``int``[] arr, ``int` `n)``    ``{``        ``for` `(``int` `i = ``0``; i < n; i++) {``            ``System.out.print(arr[i] + ``" "``);``        ``}``        ``System.out.print(``"\n"``);``    ``}` `    ``// Driver code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int``[] arr = { -``2``, ``7``,  ``15``,  -``14``, ``0``, ``15``,  ``0``, ``7``,``                      ``-``7``, -``4``, -``13``, ``5``,   ``8``, -``14``, ``12` `};``        ``int` `n = arr.length;``        ``System.out.println(``"Given Array is"``);``        ``printArray(arr, n);` `        ``timSort(arr, n);` `        ``System.out.println(``"After Sorting Array is"``);``        ``printArray(arr, n);``    ``}``}` `// This code has been contributed by 29AjayKumar`

## Python3

 `# Python3 program to perform basic timSort``MIN_MERGE ``=` `32`  `def` `calcMinRun(n):``    ``"""Returns the minimum length of a``    ``run from 23 - 64 so that``    ``the len(array)/minrun is less than or``    ``equal to a power of 2.` `    ``e.g. 1=>1, ..., 63=>63, 64=>32, 65=>33,``    ``..., 127=>64, 128=>32, ...``    ``"""``    ``r ``=` `0``    ``while` `n >``=` `MIN_MERGE:``        ``r |``=` `n & ``1``        ``n >>``=` `1``    ``return` `n ``+` `r`  `# This function sorts array from left index to``# to right index which is of size atmost RUN``def` `insertionSort(arr, left, right):``    ``for` `i ``in` `range``(left ``+` `1``, right ``+` `1``):``        ``j ``=` `i``        ``while` `j > left ``and` `arr[j] < arr[j ``-` `1``]:``            ``arr[j], arr[j ``-` `1``] ``=` `arr[j ``-` `1``], arr[j]``            ``j ``-``=` `1`  `# Merge function merges the sorted runs``def` `merge(arr, l, m, r):` `    ``# original array is broken in two parts``    ``# left and right array``    ``len1, len2 ``=` `m ``-` `l ``+` `1``, r ``-` `m``    ``left, right ``=` `[], []``    ``for` `i ``in` `range``(``0``, len1):``        ``left.append(arr[l ``+` `i])``    ``for` `i ``in` `range``(``0``, len2):``        ``right.append(arr[m ``+` `1` `+` `i])` `    ``i, j, k ``=` `0``, ``0``, l` `    ``# after comparing, we merge those two array``    ``# in larger sub array``    ``while` `i < len1 ``and` `j < len2:``        ``if` `left[i] <``=` `right[j]:``            ``arr[k] ``=` `left[i]``            ``i ``+``=` `1` `        ``else``:``            ``arr[k] ``=` `right[j]``            ``j ``+``=` `1` `        ``k ``+``=` `1` `    ``# Copy remaining elements of left, if any``    ``while` `i < len1:``        ``arr[k] ``=` `left[i]``        ``k ``+``=` `1``        ``i ``+``=` `1` `    ``# Copy remaining element of right, if any``    ``while` `j < len2:``        ``arr[k] ``=` `right[j]``        ``k ``+``=` `1``        ``j ``+``=` `1`  `# Iterative Timsort function to sort the``# array[0...n-1] (similar to merge sort)``def` `timSort(arr):``    ``n ``=` `len``(arr)``    ``minRun ``=` `calcMinRun(n)` `    ``# Sort individual subarrays of size RUN``    ``for` `start ``in` `range``(``0``, n, minRun):``        ``end ``=` `min``(start ``+` `minRun ``-` `1``, n ``-` `1``)``        ``insertionSort(arr, start, end)` `    ``# Start merging from size RUN (or 32). It will merge``    ``# to form size 64, then 128, 256 and so on ....``    ``size ``=` `minRun``    ``while` `size < n:` `        ``# Pick starting point of left sub array. We``        ``# are going to merge arr[left..left+size-1]``        ``# and arr[left+size, left+2*size-1]``        ``# After every merge, we increase left by 2*size``        ``for` `left ``in` `range``(``0``, n, ``2` `*` `size):` `            ``# Find ending point of left sub array``            ``# mid+1 is starting point of right sub array``            ``mid ``=` `min``(n ``-` `1``, left ``+` `size ``-` `1``)``            ``right ``=` `min``((left ``+` `2` `*` `size ``-` `1``), (n ``-` `1``))` `            ``# Merge sub array arr[left.....mid] &``            ``# arr[mid+1....right]``            ``if` `mid < right:``                ``merge(arr, left, mid, right)` `        ``size ``=` `2` `*` `size`  `# Driver program to test above function``if` `__name__ ``=``=` `"__main__"``:` `    ``arr ``=` `[``-``2``, ``7``, ``15``, ``-``14``, ``0``, ``15``, ``0``,``           ``7``, ``-``7``, ``-``4``, ``-``13``, ``5``, ``8``, ``-``14``, ``12``]` `    ``print``(``"Given Array is"``)``    ``print``(arr)` `    ``# Function Call``    ``timSort(arr)` `    ``print``(``"After Sorting Array is"``)``    ``print``(arr)``   `

## C#

 `// C# program to perform TimSort.``using` `System;`` ` `class` `GFG``{``    ``public` `const` `int` `RUN = 32;``    ` `    ``// This function sorts array from left index to``    ``// to right index which is of size atmost RUN``    ``public` `static` `void` `insertionSort(``int``[] arr,``                                ``int` `left, ``int` `right)``    ``{``        ``for` `(``int` `i = left + 1; i <= right; i++)``        ``{``            ``int` `temp = arr[i];``            ``int` `j = i - 1;``            ``while` `(j >= left && arr[j] > temp)``            ``{``                ``arr[j+1] = arr[j];``                ``j--;``            ``}``            ``arr[j+1] = temp;``        ``}``    ``}``      ` `    ``// merge function merges the sorted runs``    ``public` `static` `void` `merge(``int``[] arr, ``int` `l,``                                   ``int` `m, ``int` `r)``    ``{``        ``// original array is broken in two parts``        ``// left and right array``        ``int` `len1 = m - l + 1, len2 = r - m;``        ``int``[] left = ``new` `int``[len1];``        ``int``[] right = ``new` `int``[len2];``        ``for` `(``int` `x = 0; x < len1; x++)``            ``left[x] = arr[l + x];``        ``for` `(``int` `x = 0; x < len2; x++)``            ``right[x] = arr[m + 1 + x];``      ` `        ``int` `i = 0;``        ``int` `j = 0;``        ``int` `k = l;``      ` `        ``// After comparing, we merge those two array``        ``// in larger sub array``        ``while` `(i < len1 && j < len2)``        ``{``            ``if` `(left[i] <= right[j])``            ``{``                ``arr[k] = left[i];``                ``i++;``            ``}``            ``else``            ``{``                ``arr[k] = right[j];``                ``j++;``            ``}``            ``k++;``        ``}``      ` `        ``// Copy remaining elements``        ``// of left, if any``        ``while` `(i < len1)``        ``{``            ``arr[k] = left[i];``            ``k++;``            ``i++;``        ``}``      ` `        ``// Copy remaining element``        ``// of right, if any``        ``while` `(j < len2)``        ``{``            ``arr[k] = right[j];``            ``k++;``            ``j++;``        ``}``    ``}``      ` `    ``// Iterative Timsort function to sort the``    ``// array[0...n-1] (similar to merge sort)``    ``public` `static` `void` `timSort(``int``[] arr, ``int` `n)``    ``{``        ` `        ``// Sort individual subarrays of size RUN``        ``for` `(``int` `i = 0; i < n; i+=RUN)``            ``insertionSort(arr, i,``                         ``Math.Min((i+RUN-1), (n-1)));``      ` `        ``// Start merging from size RUN (or 32).``        ``// It will merge``        ``// to form size 64, then``        ``// 128, 256 and so on ....``        ``for` `(``int` `size = RUN; size < n;``                                 ``size = 2*size)``        ``{``            ` `            ``// Pick starting point of``            ``// left sub array. We``            ``// are going to merge``            ``// arr[left..left+size-1]``            ``// and arr[left+size, left+2*size-1]``            ``// After every merge, we increase``            ``// left by 2*size``            ``for` `(``int` `left = 0; left < n;``                                  ``left += 2*size)``            ``{``                ` `                ``// Find ending point of left sub array``                ``// mid+1 is starting point of``                ``// right sub array``                ``int` `mid = left + size - 1;``                ``int` `right = Math.Min((left +``                                    ``2*size - 1), (n-1));``      ` `                ``// Merge sub array arr[left.....mid] &``                ``// arr[mid+1....right]``                  ``if``(mid < right)``                    ``merge(arr, left, mid, right);``            ``}``        ``}``    ``}``      ` `    ``// Utility function to print the Array``    ``public` `static` `void` `printArray(``int``[] arr, ``int` `n)``    ``{``        ``for` `(``int` `i = 0; i < n; i++)``            ``Console.Write(arr[i] + ``" "``);``        ``Console.Write(``"\n"``);``    ``}``      ` `    ``// Driver program to test above function``    ``public` `static` `void` `Main()``    ``{``        ``int``[] arr = {-2, 7, 15, -14, 0, 15, 0,``                   ``7, -7, -4, -13, 5, 8, -14, 12};``        ``int` `n = arr.Length;``        ``Console.Write(``"Given Array is\n"``);``        ``printArray(arr, n);``      ` `        ``// Function Call``        ``timSort(arr, n);``      ` `        ``Console.Write(``"After Sorting Array is\n"``);``        ``printArray(arr, n);``    ``}   ``}` `//This code is contributed by DrRoot_`

## Javascript

 ``

Output:

```Given Array is
-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12
After Sorting Array is
-14  -14  -13  -7  -4  -2  0  0  5  7  7  8  12  15  15```

Complexity Analysis:

Complexity Comparison with Merge and Quick Sort:

References :
https://svn.python.org/projects/python/trunk/Objects/listsort.txt
https://en.wikipedia.org/wiki/Timsort#Minimum_size_.28minrun.29
This article is contributed by Aditya Kumar. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

My Personal Notes arrow_drop_up