The Timsort algorithm incorporates the well-known sorting methods, Insertion and merge sort algorithms, in its implementation.
The process of implementing Timsort is fairly straightforward: the initial step involves breaking down the given input array into segments known as runs. By organizing the data into these runs, the application of the two sorting methods is facilitated. Each run is individually sorted using the insertion sort algorithm. Subsequently, the sorted runs are merged together using the merge sort's combining function.
C++ code
Example
//Here, we are writing down the C++ programming language code to demonstrate
//the concept of Timsort Implementation Using C++ with its output
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32;
// This function sorts the array from the left index to
// to the right index, which is of size almost 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;
}
}
// this is the function we are writing to merge the sorted RUNS
void merge(int arr[], int l, int m, int r)
{
// the original array, which is like the input to our code
// is broken into left and right arrays (two parts easy for comparison)
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;
// once the comparison part is done, we have to merge the two arrays
// into a single large sub-array
while (i < len1 && j < len2)
{
if (left[i] <= right[j])
{
arr[k] = left[i];
i++;
}
else
{
arr[k] = right[j];
j++;
}
k++;
}
// the below while loop copies the elements which are present to the
// left (if any)
while (i < len1)
{
arr[k] = left[i];
k++;
i++;
}
// the below while loop copies the elements which are present to the
// right (if any)
while (j < len2)
{
arr[k] = right[j];
k++;
j++;
}
}
// below function code snippet implements the timsort algorithm
//, a combination of both insertion and merge sort algos.
void tim_Sort_(int arr[], int n)
{
// Sort individual subarrays of size RUN
// below for loop which we have created sorts the sub-arrays which are
// made individually of the size RUN
for (int i = 0; i < n; i+=RUN)
insertionSort(arr, i, min((i+RUN-1),
(n-1)));
// the runs which we have created from size 32 will merge to form
// the size of nearly 64 to 128 and 256, and it goes on ...
for (int size = RUN; size < n;
size = 2*size)
{
// picking the starting of the left sub-array
// then it will be increased by two (*2)
for (int left = 0; left < n;
left += 2*size)
{
// below are small code snippets to help us with
// rearrangement of the left and right sub-array indices from
// starting and ending
int mid = left + size - 1;
int right = min((left + 2*size - 1),
(n-1));
// below code helps us with the recombining of the runs using
// the merge sort functionality
if(mid < right)
merge(arr, left, mid, right);
}
}
}
// below function prints the array created
void print_Array_(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// below, we are writing down the drive code for timsort
int main()
{
int arr[] = {-12, 17, 15, -14, 0, 15, 0, 17, -17,
-14, -13, 15, 18, -14, 12};
int n = sizeof(arr)/sizeof(arr[0]);
printf("the given array as input is : \n");
print_Array_(arr, n);
// calling the timsort function to perform its task
tim_Sort_(arr, n);
printf("Array after implementing the sorting : \n");
print_Array_(arr, n);
return 0;
}
Output:
Output
the given array as input is :
-12 17 15 -14 0 15 0 17 -17 -14 -13 15 18 -14 12
Array after implementing the sorting :
-17 -14 -14 -14 -13 -12 0 0 12 15 15 15 17 17 18
