timsort C++ code example

Example: 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
        }
    }
}