timsort in c++
// C++ program to perform TimSort.
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32;
// 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)));//Simple insertionsort
// 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);//Simple mergesort
}
}
}