The  timsort is also a comparison-based sorting technique but it is different from other commonly used sorting methods. 

Timsort can be defined as a hybrid sorting technique as it combines both insertion sort and merge sort to sort a set of elements


The array is divided into a number of blocks which is known as the run. Now, this run will be sorted using the insertion sort technique. After sorting each run, the runs will now be merged using the ‘merge sort’ technique to get the sorted array. It is not an in-place sorting algorithm as for merging it requires extra memory space. As it combines two different sorting techniques together the performance is better than bubble or selection sort.



Suppose there is an array of 8 elements as follows:



Here the maximum number of elements is taken as 32. First, the array will be divided into a number of runs. In this example suppose the run is taken as follows:



Now, the whole array is divided into three parts called run. 1st part is of three elements, 2nd part is of 2 elements and 3rd part is of 3 elements.


Now for each the part of array, the insertion sort function will be called and each part will be sorted using the insertion sort technique.


After sorting each run we will get the following array:



Now, these three parts of the array will be merged using the merge sort technique in sorted order. 

The recursion tree of merge sort will be:



So, we get the sorted array.


INPUT: An unsorted array [98,34,12,.........,n]

OUTPUT: A sorted array[12,34,...............,n]


Step 1: [Take the inputs from the user]

Read n
For i=0 to n repeat
Read arr[i]

Step 2: [Sort the array elements]
for i = 0 to n repeat 
			if (i+31)<(n-1) then
				Call the function insertionSort for left sub array 
				Call the function insertionSort for right sub array
Set i<-i+run
		for size = RUN  to n repeat size = 2*size)
			for left = 0 to n repeat 
			Set mid <- left + size - 1 
			if (left + 2*size - 1)<(n-1) then
				Set right<-(left + 2*size - 1)
				Set right<-n-1
Calling the function merge to merge the two sub arrays in sorted order
Set left<-left+(2*size)
		[End of ‘for’ loop]
Set size=(2*size)
[End of ‘for’ loop]
Step 3: [Insertion Sort the array elements]

for i = left + 1 to right repeat
			Set temp <- arr[i] 
			Set j <- i - 1 
			while arr[j] > temp and j >= left repeat
				Set arr[j+1] <- arr[j] 
				Set j<-j-1 
			[End of ‘while’ loop]
			Set arr[j+1] <- temp
[End of ‘for’ loop]

Step 4:[Merging two sub arrays]

Set len1<-m - l + 1
Set len2 <- r - m
		for i = 0 to len1 repeat
			Set left[i] <- arr[l + i] 
[End of ‘for’ loop]
		for i = 0 to len2
			Set right[i] <- arr[m + 1 + i]
[End of ‘for’ loop]
		Set i <- 0 
		Set j <- 0
		Set k <- l 
		while i < len1 and j < len2 repeat 
			if left[i] ≤ right[j] then 
				Set arr[k] <- left[i]
				Set i<-i+1 
				Set arr[k] <- right[j] 
				Set j=j+1
Set k<-k+1
		[End of ‘while’ loop]
		while i < len1 repeat
			Set arr[k] <- left[i] 
			Set k<-k+1 
			Set i<-i+1 
[End of ‘while’ loop]s
while j < len2 repeat
			Set arr[k] <- right[j] 
			Set k<-k+1 
			Set j<-j+1 
		[End of ‘while’ loop]
[End of function ‘merge’]
Step 5:[Display the sorted array]
For i=0 to n
Print arr[i]

Step 6: Stop.



1. It is a comparison-based sorting algorithm.


2. It is a hybrid sorting technique that uses insertion sort and merges sort together.


3. It is more efficient than a bubble or selection sort.



The best-case occurs when the array is already sorted. 


The average-case and worst-case complexity of timsort is similar to that of the merge sort algorithm


Hence it is called one of the best and efficient sorting algorithms.




In the time of merging it requires extra memory spaces. 



1. It is a stable sorting technique.


2. It is faster than the old merge sort.


3. The worst-case complexity is also O(nlogn).



1. There are no such disadvantages of timsort as it is an efficient sorting algorithm.



1. From version 2.3 onwards python uses timsort as its sorting algorithm.


2. For sorting arrays of non-primitive type in java, SE 7 on the android platform or google chrome timsort is used as a sorting algorithm.

Contributed by