## Tim Sort

Back to Programming

### Description

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.

### Algorithm

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

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

PROCESS:

Step 1: [Take the inputs from the user]

For i=0 to n repeat

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

### Code

CHARACTERISTICS:

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.

TIME COMPLEXITY:

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.

SPACE COMPLEXITY: 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.

APPLICATION:

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.

Related