CREATE OWN LIBRARY

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.

PROCEDURE WITH EXAMPLE:

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]

PROCESS:

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 
			else
				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)
			else
				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 
			else
				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.