Skip to main content

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
Last updated on by Kalkicode




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.

New Comment