1// C++ program to perform TimSort.
2#include<bits/stdc++.h>
3using namespace std;
4const int RUN = 32;
5
6// Iterative Timsort function to sort the array[0...n-1] (similar to merge sort)
7void timSort(int arr[], int n){
8 // Sort individual subarrays of size RUN
9 for (int i = 0; i < n; i+=RUN)
10 insertionSort(arr, i, min((i+RUN-1),(n-1)));//Simple insertionsort
11 // Start merging from size RUN (or 32).
12 // It will merge to form size 64, then 128, 256 and so on ....
13 for (int size = RUN; size < n;size = 2*size){
14 // 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]
15 // After every merge, we increase left by 2*size
16 for (int left = 0; left < n;left += 2*size){
17 // find ending point of left sub array mid+1 is starting point of right sub array
18 int mid = left + size - 1;
19 int right = min((left + 2*size - 1),(n-1));
20 // merge sub array arr[left.....mid] & arr[mid+1....right]
21 if(mid < right)
22 merge(arr, left, mid, right);//Simple mergesort
23 }
24 }
25}
26