# Timsort

Timsort is a sorting algorithm that combines insertion sort and merge sort techniques to achieve efficient and stable sorting of arrays. It was designed to perform well on many kinds of real-world data, including data with natural ordering, and it has been adopted as the default sorting algorithm in many programming languages, including Python and Java.

Timsort works by dividing the input array into small subarrays, sorting them using insertion sort, and then merging the sorted subarrays using a modified form of merge sort. The algorithm uses a technique called "galloping mode" to improve the efficiency of the merge step by taking advantage of the fact that the subarrays are often already partially sorted.

The basic steps of Timsort are as follows:

1. Divide the input array into subarrays of size 32 or less.
2. Sort the subarrays using insertion sort.
3. Merge the sorted subarrays using a modified form of merge sort that takes advantage of partially sorted runs.
4. Repeat steps 1-3 until the entire array is sorted.

Timsort has a worst-case time complexity of O(n log n) and a best-case time complexity of O(n). It is also designed to be stable, meaning that it preserves the relative order of equal elements in the input array.

Here given code implementation process.

``````// C Program
// Sort array elements by using timsort
#include <stdio.h>

//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
void insertion_sort(int arr[], int start, int last)
{
int i = 0;
int j = 0;
for (i = start; i < last - 1; ++i)
{
j = i + 1;
while (j > start && arr[j - 1] > arr[j])
{
//Swap array element
swap_data(arr, j, j - 1);
j--;
}
}
}
//Sorted merge of given two subarrays of an array
void merge_elements(int arr[], int front, int tail, int middle)
{
//Get the size of first subarray
int s1 = (middle - front) + 1;
//Get the size of second subarray
int s2 = tail - middle;
//Creating auxiliary storage to store elements
int first_subarray[s1];
int second_subarray[s2];
//Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = arr[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = arr[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
arr[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
arr[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
//return a minimum value of two numbers
int min_element(int first, int second)
{
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
void tim_sort(int arr[], int n)
{
//Loop controlling variables
int i = 0;
int start = 0;
int middle = 0;
int last = 0;
//Set run size
//32, 64, 128, 256
int run = 32;
for (i = 0; i < n; i += run)
{
insertion_sort(arr, i, min_element((i + 31), (n)));
}
for (i = run; i < n; i = 2 * i)
{
for (start = 0; start < n; start += 2 * i)
{
middle = start + i - 1;
last = min_element((start + 2 * i - 1), (n));
merge_elements(arr, start, last, middle);
}
}
}
int main()
{
//Define an array of integers
int arr1[] = {
3,
6,
2,
5,
-7,
2,
1,
4,
7,
8,
2
};
//Get the size of arr
int size = sizeof(arr1) / sizeof(arr1[0]);
//Before sort
printf("\n  Before Sort  :\n");
display(arr1, size);
//Sort element
tim_sort(arr1, size);
//After sort
printf("\n  After Sort  :\n");
display(arr1, size);
int arr2[] = {
8,
2,
9,
-6,
3,
2,
31,
41,
2,
1,
67,
32
};
//Get the size of arr
size = sizeof(arr2) / sizeof(arr2[0]);
//Before sort
printf("\n  Before Sort  :\n");
display(arr2, size);
//Sort element
tim_sort(arr2, size);
//After sort
printf("\n  After Sort  :\n");
display(arr2, size);
return 0;
}``````

#### Output

``````  Before Sort  :
3  6  2  5  -7  2  1  4  7  8  2

After Sort  :
-7  1  2  2  2  3  4  5  6  7  8

Before Sort  :
8  2  9  -6  3  2  31  41  2  1  67  32

After Sort  :
-6  1  2  2  2  3  8  9  31  32  41  67``````
``````/*
Java Program
Sort array elements by using timsort
*/
class MySort
{
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
// Swapping the array elements in given location
public void swap_data(int[] arr, int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
public void insertion_sort(int[] arr, int start, int last)
{
int i = 0;
int j = 0;
for (i = start; i < last - 1; ++i)
{
j = i + 1;
while (j > start && arr[j - 1] > arr[j])
{
//Swap array element
swap_data(arr, j, j - 1);
j--;
}
}
}
//Sorted merge of given two subarrays of an array
public void merge_elements(int[] arr, int front, int tail, int middle)
{
//Get the size of first subarray
int s1 = (middle - front) + 1;
//Get the size of second subarray
int s2 = tail - middle;
//Creating auxiliary storage to store elements
int[] first_subarray = new int[s1];
int[] second_subarray = new int[s2];
//Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = arr[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = arr[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
arr[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
arr[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
//return a minimum value of two numbers
public int min_element(int first, int second)
{
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
public void tim_sort(int[] arr, int n)
{
//Loop controlling variables
int i = 0;
int start = 0;
int middle = 0;
int last = 0;
//Set run size
//32, 64, 128, 256
int run = 32;
for (i = 0; i < n; i += run)
{
insertion_sort(arr, i, min_element((i + 31), (n)));
}
for (i = run; i < n; i = 2 * i)
{
for (start = 0; start < n; start += 2 * i)
{
middle = start + i - 1;
last = min_element((start + 2 * i - 1), (n));
merge_elements(arr, start, last, middle);
}
}
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define an array of integers
int[] arr = {
3,
6,
2,
5,
-7,
2,
1,
4,
7,
8,
2
};
//Get the size
int size = arr.length;;
System.out.print("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.tim_sort(arr, size);
System.out.print("\n After Sort :\n");
obj.display(arr, size);
int[] arr1 = {
8,
2,
9,
-6,
3,
2,
31,
41,
2,
1,
67,
32
};
//Get the size
size = arr1.length;
System.out.print("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tim_sort(arr1, size);
System.out.print("\n After Sort :\n");
obj.display(arr1, size);
}
}``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67``````
``````//Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Sort array elements by using timsort
*/
class MySort
{
public:
//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
void insertion_sort(int arr[], int start, int last)
{
int i = 0;
int j = 0;
for (i = start; i < last - 1; ++i)
{
j = i + 1;
while (j > start && arr[j - 1] > arr[j])
{
//Swap array element
this->swap_data(arr, j, j - 1);
j--;
}
}
}
//Sorted merge of given two subarrays of an array
void merge_elements(int arr[], int front, int tail, int middle)
{
//Get the size of first subarray
int s1 = (middle - front) + 1;
//Get the size of second subarray
int s2 = tail - middle;
int first_subarray[s1];
int second_subarray[s2];
//Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = arr[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = arr[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
arr[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
arr[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
//return a minimum value of two numbers
int min_element(int first, int second)
{
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
void tim_sort(int arr[], int n)
{
//Loop controlling variables
int i = 0;
int start = 0;
int middle = 0;
int last = 0;
//Set run size
//32, 64, 128, 256
int run = 32;
for (i = 0; i < n; i += run)
{
this->insertion_sort(arr, i, this->min_element((i + 31), (n)));
}
for (i = run; i < n; i = 2 * i)
{
for (start = 0; start < n; start += 2 * i)
{
middle = start + i - 1;
last = this->min_element((start + 2 * i - 1), (n));
this->merge_elements(arr, start, last, middle);
}
}
}
};
int main()
{
MySort obj = MySort();
int arr[] = {
3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);;
cout << "\n Befre Sort :\n";
obj.display(arr, size);
//Sort element
obj.tim_sort(arr, size);
cout << "\n After Sort :\n";
obj.display(arr, size);
int arr1[] = {
8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
};
//Get the size
size = sizeof(arr1) / sizeof(arr1[0]);
cout << "\n Before Sort :\n";
obj.display(arr1, size);
//Sort element
obj.tim_sort(arr1, size);
cout << "\n After Sort :\n";
obj.display(arr1, size);
return 0;
}``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67``````
``````//Include namespace system
using System;
/*
C# Program
Sort array elements by using timsort
*/
class MySort
{
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
// Swapping the array elements in given location
public void swap_data(int[] arr, int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
public void insertion_sort(int[] arr, int start, int last)
{
int i = 0;
int j = 0;
for (i = start; i < last - 1; ++i)
{
j = i + 1;
while (j > start && arr[j - 1] > arr[j])
{
//Swap array element
swap_data(arr, j, j - 1);
j--;
}
}
}
//Sorted merge of given two subarrays of an array
public void merge_elements(int[] arr, int front, int tail, int middle)
{
//Get the size of first subarray
int s1 = (middle - front) + 1;
//Get the size of second subarray
int s2 = tail - middle;
int[] first_subarray = new int[s1];
int[] second_subarray = new int[s2];
//Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = arr[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = arr[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
arr[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
arr[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
//return a minimum value of two numbers
public int min_element(int first, int second)
{
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
public void tim_sort(int[] arr, int n)
{
//Loop controlling variables
int i = 0;
int start = 0;
int middle = 0;
int last = 0;
//Set run size
//32, 64, 128, 256
int run = 32;
for (i = 0; i < n; i += run)
{
insertion_sort(arr, i, min_element((i + 31), (n)));
}
for (i = run; i < n; i = 2 * i)
{
for (start = 0; start < n; start += 2 * i)
{
middle = start + i - 1;
last = min_element((start + 2 * i - 1), (n));
merge_elements(arr, start, last, middle);
}
}
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] arr = {
3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
};
//Get the size
int size = arr.Length;;
Console.Write("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.tim_sort(arr, size);
Console.Write("\n After Sort :\n");
obj.display(arr, size);
int[] arr1 = {
8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
};
//Get the size
size = arr1.Length;
Console.Write("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tim_sort(arr1, size);
Console.Write("\n After Sort :\n");
obj.display(arr1, size);
}
}``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67``````
``````<?php
/*
Php Program
Sort array elements by using timsort
*/
class MySort
{
//Function which is display arr elements
public	function display( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
// Swapping the array elements in given location
public	function swap_data( & \$arr, \$first, \$second)
{
\$temp = \$arr[\$first];
\$arr[\$first] = \$arr[\$second];
\$arr[\$second] = \$temp;
}
// Perform the insertion sort in given array
public	function insertion_sort( & \$arr, \$start, \$last)
{
\$i = 0;
\$j = 0;
for (\$i = \$start; \$i < \$last - 1; ++\$i)
{
\$j = \$i + 1;
while (\$j > \$start && \$arr[\$j - 1] > \$arr[\$j])
{
//Swap array element
\$this->swap_data(\$arr, \$j, \$j - 1);
\$j--;
}
}
}
//Sorted merge of given two subarrays of an array
public	function merge_elements( & \$arr, \$front, \$tail, \$middle)
{
//Get the size of first subarray
\$s1 = (\$middle - \$front) + 1;
//Get the size of second subarray
\$s2 = \$tail - \$middle;
//Creating auxiliary storage to store elements
\$first_subarray = array_fill(0, \$s1, 0);
\$second_subarray = array_fill(0, \$s2, 0);
//Loop controlling variables
\$i = 0;
\$j = 0;
\$counter = 0;
//Get the elements of first subarray
for (\$i = 0; \$i < \$s1; \$i++)
{
\$first_subarray[\$i] = \$arr[\$front + \$i];
}
//Get the elements of second subarray
for (\$i = 0; \$i < \$s2; \$i++)
{
\$second_subarray[\$i] = \$arr[\$middle + \$i + 1];
}
\$i = 0;
// Add sorted elements into actual array
while (\$counter < \$s1 + \$s2)
{
//Check that both sub array element exists or not
if (\$i < \$s1 && \$j < \$s2)
{
if (\$first_subarray[\$i] <= \$second_subarray[\$j])
{
//When first array [i] element are smaller
\$arr[\$front + \$counter] = \$first_subarray[\$i];
\$i++;
}
else
{
//When second array [j] element are smaller
\$arr[\$front + \$counter] = \$second_subarray[\$j];
\$j++;
}
}
else if (\$i < \$s1)
{
//When first sub array element exists
\$arr[\$front + \$counter] = \$first_subarray[\$i];
\$i++;
}
else
{
//When second sub array element exists
\$arr[\$front + \$counter] = \$second_subarray[\$j];
\$j++;
}
\$counter++;
}
}
//return a minimum value of two numbers
public	function min_element(\$first, \$second)
{
if (\$first < \$second)
{
//When first number is minimum
return \$first;
}
return \$second;
}
//Executing the timsort in given array
public	function tim_sort( & \$arr, \$n)
{
//Loop controlling variables
\$i = 0;
\$start = 0;
\$middle = 0;
\$last = 0;
//Set run size
//32, 64, 128, 256
\$run = 32;
for (\$i = 0; \$i < \$n; \$i += \$run)
{
\$this->insertion_sort(\$arr, \$i, \$this->min_element((\$i + 31), (\$n)));
}
for (\$i = \$run; \$i < \$n; \$i = 2 * \$i)
{
for (\$start = 0; \$start < \$n; \$start += 2 * \$i)
{
\$middle = \$start + \$i - 1;
\$last = \$this->min_element((\$start + 2 * \$i - 1), (\$n));
\$this->merge_elements(\$arr, \$start, \$last, \$middle);
}
}
}
}

function main()
{
\$obj = new MySort();
//Define an array of integers
\$arr = array(3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2);
//Get the size
\$size = count(\$arr);;
echo "\n Befre Sort :\n";
\$obj->display(\$arr, \$size);
//Sort element
\$obj->tim_sort(\$arr, \$size);
echo "\n After Sort :\n";
\$obj->display(\$arr, \$size);
\$arr1 = array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32);
//Get the size
\$size = count(\$arr1);
echo "\n Before Sort :\n";
\$obj->display(\$arr1, \$size);
//Sort element
\$obj->tim_sort(\$arr1, \$size);
echo "\n After Sort :\n";
\$obj->display(\$arr1, \$size);
}
main();``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67``````
``````/*
Node Js Program
Sort array elements by using timsort
*/
class MySort
{
//Function which is display arr elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
// Swapping the array elements in given location
swap_data(arr, first, second)
{
var temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
insertion_sort(arr, start, last)
{
var i = 0;
var j = 0;
for (i = start; i < last - 1; ++i)
{
j = i + 1;
while (j > start && arr[j - 1] > arr[j])
{
//Swap array element
this.swap_data(arr, j, j - 1);
j--;
}
}
}
//Sorted merge of given two subarrays of an array
merge_elements(arr, front, tail, middle)
{
//Get the size of first subarray
var s1 = (middle - front) + 1;
//Get the size of second subarray
var s2 = tail - middle;
//Creating auxiliary storage to store elements
var first_subarray = Array(s1).fill(0);
var second_subarray = Array(s2).fill(0);
//Loop controlling variables
var i = 0;
var j = 0;
var counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = arr[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = arr[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
arr[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
arr[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
arr[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
//return a minimum value of two numbers
min_element(first, second)
{
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
tim_sort(arr, n)
{
//Loop controlling variables
var i = 0;
var start = 0;
var middle = 0;
var last = 0;
//Set run size
//32, 64, 128, 256
var run = 32;
for (i = 0; i < n; i += run)
{
this.insertion_sort(arr, i, this.min_element((i + 31), (n)));
}
for (i = run; i < n; i = 2 * i)
{
for (start = 0; start < n; start += 2 * i)
{
middle = start + i - 1;
last = this.min_element((start + 2 * i - 1), (n));
this.merge_elements(arr, start, last, middle);
}
}
}
}

function main()
{
var obj = new MySort();
//Define an array of integers
var arr = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2];
//Get the size
var size = arr.length;;
process.stdout.write("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.tim_sort(arr, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr, size);
var arr1 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32];
//Get the size
size = arr1.length;
process.stdout.write("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tim_sort(arr1, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr1, size);
}
main();``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67``````
``````# 	Python 3 Program
# 	Sort array elements by using timsort

class MySort :
# Function which is display arr elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

#  Swapping the array elements in given location
def swap_data(self, arr, first, second) :
temp = arr[first]
arr[first] = arr[second]
arr[second] = temp

#  Perform the insertion sort in given array
def insertion_sort(self, arr, start, last) :
i = 0
j = 0
i = start
while (i < last - 1) :
j = i + 1
while (j > start and arr[j - 1] > arr[j]) :
# Swap array element
self.swap_data(arr, j, j - 1)
j -= 1

i += 1

# Sorted merge of given two subarrays of an array
def merge_elements(self, arr, front, tail, middle) :
# Get the size of first subarray
s1 = (middle - front) + 1
# Get the size of second subarray
s2 = tail - middle
# Creating auxiliary storage to store elements
first_subarray = [0] * s1
second_subarray = [0] * s2
# Loop controlling variables
i = 0
j = 0
counter = 0
# Get the elements of first subarray
i = 0
while (i < s1) :
first_subarray[i] = arr[front + i]
i += 1

# Get the elements of second subarray
i = 0
while (i < s2) :
second_subarray[i] = arr[middle + i + 1]
i += 1

i = 0
#  Add sorted elements into actual array
while (counter < s1 + s2) :
# Check that both sub array element exists or not
if (i < s1 and j < s2) :
if (first_subarray[i] <= second_subarray[j]) :
# When first array [i] element are smaller
arr[front + counter] = first_subarray[i]
i += 1
else :
# When second array [j] element are smaller
arr[front + counter] = second_subarray[j]
j += 1

elif(i < s1) :
# When first sub array element exists
arr[front + counter] = first_subarray[i]
i += 1
else :
# When second sub array element exists
arr[front + counter] = second_subarray[j]
j += 1

counter += 1

# return a minimum value of two numbers
def min_element(self, first, second) :
if (first < second) :
# When first number is minimum
return first

return second

# Executing the timsort in given array
def tim_sort(self, arr, n) :
# Loop controlling variables
i = 0
start = 0
middle = 0
last = 0
# Set run size
# 32, 64, 128, 256
run = 32
i = 0
while (i < n) :
self.insertion_sort(arr, i, self.min_element((i + 31), (n)))
i += run

i = run
while (i < n) :
start = 0
while (start < n) :
middle = start + i - 1
last = self.min_element((start + 2 * i - 1), (n))
self.merge_elements(arr, start, last, middle)
start += 2 * i

i = 2 * i

def main() :
obj = MySort()
# Define an array of integers
arr = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2]
# Get the size
size = len(arr)
print("\n Befre Sort :\n", end = "")
obj.display(arr, size)
# Sort element
obj.tim_sort(arr, size)
print("\n After Sort :\n", end = "")
obj.display(arr, size)
arr1 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32]
# Get the size
size = len(arr1)
print("\n Before Sort :\n", end = "")
obj.display(arr1, size)
# Sort element
obj.tim_sort(arr1, size)
print("\n After Sort :\n", end = "")
obj.display(arr1, size)

if __name__ == "__main__": main()``````

#### Output

`````` Befre Sort :
3  6  2  5  -7  2  1  4  7  8  2

After Sort :
-7  1  2  2  2  3  4  5  6  7  8

Before Sort :
8  2  9  -6  3  2  31  41  2  1  67  32

After Sort :
-6  1  2  2  2  3  8  9  31  32  41  67``````
``````# 	Ruby Program
# 	Sort array elements by using timsort

class MySort

# Function which is display arr elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i])
i += 1
end
print("\n")
end
#  Swapping the array elements in given location
def swap_data(arr, first, second)

temp = arr[first]
arr[first] = arr[second]
arr[second] = temp
end
#  Perform the insertion sort in given array
def insertion_sort(arr, start, last)

i = 0
j = 0
i = start
while (i < last - 1)

j = i + 1
while (j > start && arr[j - 1] > arr[j])

# Swap array element
self.swap_data(arr, j, j - 1)
j -= 1
end
i += 1
end
end
# Sorted merge of given two subarrays of an array
def merge_elements(arr, front, tail, middle)

# Get the size of first subarray
s1 = (middle - front) + 1
# Get the size of second subarray
s2 = tail - middle
# Creating auxiliary storage to store elements
first_subarray = Array.new(s1) {0}
second_subarray = Array.new(s2) {0}
# Loop controlling variables
i = 0
j = 0
counter = 0
# Get the elements of first subarray
i = 0
while (i < s1)

first_subarray[i] = arr[front + i]
i += 1
end
# Get the elements of second subarray
i = 0
while (i < s2)

second_subarray[i] = arr[middle + i + 1]
i += 1
end
i = 0
#  Add sorted elements into actual array
while (counter < s1 + s2)

# Check that both sub array element exists or not
if (i < s1 && j < s2)

if (first_subarray[i] <= second_subarray[j])

# When first array [i] element are smaller
arr[front + counter] = first_subarray[i]
i += 1
else

# When second array [j] element are smaller
arr[front + counter] = second_subarray[j]
j += 1
end
elsif(i < s1)

# When first sub array element exists
arr[front + counter] = first_subarray[i]
i += 1
else

# When second sub array element exists
arr[front + counter] = second_subarray[j]
j += 1
end
counter += 1
end
end
# return a minimum value of two numbers
def min_element(first, second)

if (first < second)

# When first number is minimum
return first
end
return second
end
# Executing the timsort in given array
def tim_sort(arr, n)

# Loop controlling variables
i = 0
start = 0
middle = 0
last = 0
# Set run size
# 32, 64, 128, 256
run = 32
i = 0
while (i < n)

self.insertion_sort(arr, i, self.min_element((i + 31), (n)))
i += run
end
i = run
while (i < n)

start = 0
while (start < n)

middle = start + i - 1
last = self.min_element((start + 2 * i - 1), (n))
self.merge_elements(arr, start, last, middle)
start += 2 * i
end
i = 2 * i
end
end
end
def main()

obj = MySort.new()
# Define an array of integers
arr = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2]
# Get the size
size = arr.length
print("\n Befre Sort :\n")
obj.display(arr, size)
# Sort element
obj.tim_sort(arr, size)
print("\n After Sort :\n")
obj.display(arr, size)
arr1 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32]
# Get the size
size = arr1.length
print("\n Before Sort :\n")
obj.display(arr1, size)
# Sort element
obj.tim_sort(arr1, size)
print("\n After Sort :\n")
obj.display(arr1, size)
end
main()``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
``````
``````/*
Scala Program
Sort array elements by using timsort
*/
class MySort
{
//Function which is display arr elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
// Swapping the array elements in given location
def swap_data(arr: Array[Int], first: Int, second: Int): Unit = {
var temp: Int = arr(first);
arr(first) = arr(second);
arr(second) = temp;
}
// Perform the insertion sort in given array
def insertion_sort(arr: Array[Int], start: Int, last: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
i = start;
while (i < last - 1)
{
j = i + 1;
while (j > start && arr(j - 1) > arr(j))
{
//Swap array element
swap_data(arr, j, j - 1);
j -= 1;
}
i += 1;
}
}
//Sorted merge of given two subarrays of an array
def merge_elements(arr: Array[Int], front: Int, tail: Int, middle: Int): Unit = {
//Get the size of first subarray
var s1: Int = (middle - front) + 1;
//Get the size of second subarray
var s2: Int = tail - middle;
//Creating auxiliary storage to store elements
var first_subarray: Array[Int] = Array.fill[Int](s1)(0);
var second_subarray: Array[Int] = Array.fill[Int](s2)(0);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var counter: Int = 0;
//Get the elements of first subarray
i = 0;
while (i < s1)
{
first_subarray(i) = arr(front + i);
i += 1;
}
//Get the elements of second subarray
i = 0;
while (i < s2)
{
second_subarray(i) = arr(middle + i + 1);
i += 1;
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray(i) <= second_subarray(j))
{
//When first array [i] element are smaller
arr(front + counter) = first_subarray(i);
i += 1;
}
else
{
//When second array [j] element are smaller
arr(front + counter) = second_subarray(j);
j += 1;
}
}
else if (i < s1)
{
//When first sub array element exists
arr(front + counter) = first_subarray(i);
i += 1;
}
else
{
//When second sub array element exists
arr(front + counter) = second_subarray(j);
j += 1;
}
counter += 1;
}
}
//return a minimum value of two numbers
def min_element(first: Int, second: Int): Int = {
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
def tim_sort(arr: Array[Int], n: Int): Unit = {
//Loop controlling variables
var i: Int = 0;
var start: Int = 0;
var middle: Int = 0;
var last: Int = 0;
//Set run size
//32, 64, 128, 256
var run: Int = 32;
i = 0;
while (i < n)
{
insertion_sort(arr, i, min_element((i + 31), (n)));
i += run;
}
i = run;
while (i < n)
{
start = 0;
while (start < n)
{
middle = start + i - 1;
last = min_element((start + 2 * i - 1), (n));
merge_elements(arr, start, last, middle);
start += 2 * i;
}
i = 2 * i;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define an array of integers
var arr: Array[Int] = Array(3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2);
//Get the size
var size: Int = arr.length;
print("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.tim_sort(arr, size);
print("\n After Sort :\n");
obj.display(arr, size);
var arr1: Array[Int] = Array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32);
//Get the size
size = arr1.length;
print("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tim_sort(arr1, size);
print("\n After Sort :\n");
obj.display(arr1, size);
}
}``````

#### Output

`````` Befre Sort :
3 6 2 5 -7 2 1 4 7 8 2

After Sort :
-7 1 2 2 2 3 4 5 6 7 8

Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32

After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67``````
``````/*
Swift Program
Sort array elements by using timsort
*/
class MySort
{
//Function which is display arr elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
// Swapping the array elements in given location
func swap_data(_ arr: inout[Int], _ first: Int, _ second: Int)
{
let temp: Int = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
func insertion_sort(_ arr: inout[Int], _ start: Int, _ last: Int)
{
var i: Int = 0;
var j: Int = 0;
i = start;
while (i < last - 1)
{
j = i + 1;
while (j > start && arr[j - 1] > arr[j])
{
//Swap array element
self.swap_data(&arr, j, j - 1);
j -= 1;
}
i += 1;
}
}
//Sorted merge of given two subarrays of an array
func merge_elements(_ arr: inout[Int], _ front: Int, _ tail: Int, _ middle: Int)
{
//Get the size of first subarray
let s1: Int = (middle - front) + 1;
//Get the size of second subarray
let s2: Int = tail - middle;
//Creating auxiliary storage to store elements
var first_subarray: [Int] = Array(repeating: 0, count: s1);
var second_subarray: [Int] = Array(repeating: 0, count: s2);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var counter: Int = 0;
//Get the elements of first subarray
i = 0;
while (i < s1)
{
first_subarray[i] = arr[front + i];
i += 1;
}
//Get the elements of second subarray
i = 0;
while (i < s2)
{
second_subarray[i] = arr[middle + i + 1];
i += 1;
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
arr[front + counter] = first_subarray[i];
i += 1;
}
else
{
//When second array [j] element are smaller
arr[front + counter] = second_subarray[j];
j += 1;
}
}
else if (i < s1)
{
//When first sub array element exists
arr[front + counter] = first_subarray[i];
i += 1;
}
else
{
//When second sub array element exists
arr[front + counter] = second_subarray[j];
j += 1;
}
counter += 1;
}
}
//return a minimum value of two numbers
func min_element(_ first: Int, _ second: Int) -> Int
{
if (first < second)
{
//When first number is minimum
return first;
}
return second;
}
//Executing the timsort in given array
func tim_sort(_ arr: inout[Int], _ n: Int)
{
//Loop controlling variables
var i: Int = 0;
var start: Int = 0;
var middle: Int = 0;
var last: Int = 0;
//Set run size
//32, 64, 128, 256
let run: Int = 32;
i = 0;
while (i < n)
{
self.insertion_sort(&arr, i, self.min_element((i + 31), (n)));
i += run;
}
i = run;
while (i < n)
{
start = 0;
while (start < n)
{
middle = start + i - 1;
last = self.min_element((start + 2 * i - 1), (n));
self.merge_elements(&arr, start, last, middle);
start += 2 * i;
}
i = 2 * i;
}
}
}
func main()
{
let obj: MySort = MySort();
//Define an array of integers
var arr: [Int] = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2];
//Get the size
var size: Int = arr.count;
print("\n Befre Sort :\n", terminator: "");
obj.display(arr, size);
//Sort element
obj.tim_sort(&arr, size);
print("\n After Sort :\n", terminator: "");
obj.display(arr, size);
var arr1: [Int] = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32];
//Get the size
size = arr1.count;
print("\n Before Sort :\n", terminator: "");
obj.display(arr1, size);
//Sort element
obj.tim_sort(&arr1, size);
print("\n After Sort :\n", terminator: "");
obj.display(arr1, size);
}
main();``````

#### Output

`````` Befre Sort :
3  6  2  5  -7  2  1  4  7  8  2

After Sort :
-7  1  2  2  2  3  4  5  6  7  8

Before Sort :
8  2  9  -6  3  2  31  41  2  1  67  32

After Sort :
-6  1  2  2  2  3  8  9  31  32  41  67``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.