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

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

__ADVANTAGES:__

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

__DISADVANTAGES:__

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

- Insertion Sort
- Merge Sort using recursion
- Merge Sort Iterative
- Bitonic Sort
- Comb Sort
- Gnome sort
- Shell Sort
- Tree Sort
- List Sort
- Minmax Sort
- Intro Sort
- Cocktail Sort
- Counting Sort
- Bucket Sort
- Radix Sort for positive integer
- Heap Sort Iterative
- Heap Sort using recursion
- Quick Sort using recursion
- Quicksort Iterative
- Selection Sort
- Bubble Sort
- 3 way Merge Sort

Contributed by