Timsort是一种稳定的排序算法，它使用合并排序和插入排序的思想。它也可以称为插入和合并排序的混合算法。它广泛用于Java，Python，C和C ++内置排序算法中。该算法的思想是使用插入排序对小块进行排序，然后使用合并排序算法的合并功能合并所有大块。
在这种算法中，数组被分成小块。这些块称为RUN。使用插入排序技术获取每个RUN并对其进行排序。在对所有RUN进行排序之后，将使用合并功能将其合并。
在某些情况下，阵列的大小可能小于RUN。在这种情况下，通过插入排序技术对数组进行排序。通常，RUN块的大小从32到64不等，具体取决于阵列的大小。仅当子数组块的幂为2时，合并函数才会合并。
使用插入排序的优点是因为插入排序对于小尺寸的数组可以很好地工作。
时间复杂度-
最好的情况- Omega(n)
平均情况- O(nlogn)
最糟糕的情况 - O(nlogn)
初始化大小为32的RUN。
实现RUN大小块的插入排序。
函数merge（int arr []，int l，int m，int r）将一个数组，左元素，该数组的中间和该数组的右元素作为输入。该函数返回大小为32的合并排序块。
初始化具有所有左侧元素的数组的长度和具有所有右侧元素的数组的长度。
填充左数组和右数组后，遍历左数组和右数组。
如果左侧数组中的元素小于右侧数组中的元素，则将其推入更大的数组中。
否则，将元素相应地推入较小的数组。
将左数组和右数组中的其余元素复制到更大的数组中。
timSortAlgo（int arr []，int n）函数将一个数组及其大小作为输入。最初会调用插入Sort并合并数组元素。
使用Tim Sort将输出作为数组的最终元素返回。
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // 初始化RUN以获取块
void insertionSort(int arr[], int left, int right) // 实施插入
sort for RUN size chunks{
for (int i = left + 1; i <= right; i++){
int t = arr[i];
int j = i - 1;
while (j >= left && t < arr[j]){
arr[j+1] = arr[j--];
}
arr[j+1] = t;
}
}
void merge(int arr[], int l, int m, int r) // 使用合并功能
sorted chunks of size 32 are merged into one{
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;
while (i < len1 && j < len2) // 左右迭代两个数组{
if (left[i] <= right[j]) // 如果左侧的元素小于，则通过推入更大的数组来增加i {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j]; // 右数组中的元素更大
increment j
j++;
}
k++;
}
while (i < len1) // 此循环会复制左侧数组中的剩余元素{
arr[k] = left[i];
k++;
i++;
}
while (j < len2) // 此循环将右数组中的其余元素复制{
arr[k] = right[j];
k++;
j++;
}
}
void timSortAlgo(int arr[], int n){
for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); //呼叫insertSort()
for (int s = RUN; s < n; s = 2*s) //从大小RUN（或32）开始合并。它将持续到2 * RUN {
//选择左子数组的起点。我们要合并
arr[left..left+size-1]
// 和arr [left + size，left + 2 * size-1]
// 每次合并后，我们
// 向左增加2 *大小
for (int left = 0; left < n;left += 2*s){
int mid = left + s - 1; // 找到左子的终点
array mid+1 is starting point of right sub array
int right = min((left + 2*s - 1), (n-1));
merge(arr, left, mid, right); // 合并子数组
arr[left.....mid] & arr[mid+1....right]
}
}
}
void printArray(int arr[], int n){
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
// 实现timsort算法的主要功能
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[0]);
cout << "The Original array- ";
printArray(arr, n);
// 调用timsortAlgo函数对数组进行排序
timSortAlgo(arr, n);
cout<<"After Sorting Array Using TimSort Algorithm- ";
printArray(arr, n); // 调用打印功能
return 0;
}