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