The word ‘**Sorting**’ means arranging the elements in either ascending or descending order. The **insertion sort** is a simple sorting technique that is based on the **principle of insertion of any element in the required position** i.e. the sorting is done in such a way it seems like the new element is inserted at its sorted position at that particular time which makes this sorting technique different from ‘bubble sort’ or ‘selection sort’. If there is n number of elements then it will require n-1 iterations to sort the elements.

__PROCEDURE WITH EXAMPLE:__

Suppose there are **5 elements** in an array as below and we want to sort them in ascending order. As **the number of elements is 5 then it will need 5 - 1 = ****4** steps to sort the array. The **first cell is containing the element ‘****12****’**. If we imagine the array with only one element ‘**12**’ then it need not be sorted.

From the second element, the sorting will be taken place and the steps are as follows:

__Step-1:__

In this step consider that the **new element ‘****54****’** has to be inserted into the array. So first the element ‘**54**’ is **compared with the previously existing element ‘****12****’** **but as it is already in a sorted** order so no shifting of elements will be needed.

__Step-2:__

Similar to **Step 1**, here also **65**** is inserted in its sorted position** which does **not need any shifting** **of elements** as it is greater than both ‘**54**’ and ’**12**’.

__Step-3:__

Now the **new element is ‘****32****’** **which is to be inserted in the array**. Before inserting it when it is **compared to its previous element ‘****65****’** it is fount that **‘****32****’ is lesser than ‘****65****’** so the **element ‘****65****’ is shifted to its one position right**. Then again it is **compared to ‘****54****’** which is also **greater than ‘****32****’ so that ‘****54****’** is also shifted to its one position right and the array will look like below before positioning ‘**32**’ into its proper position.

After this the **element ‘****32****’** will be inserted in its current sorted position and the array will be:

__Step 4:__

The last element to be **inserted into the array is ‘****9****’**. Similar to Step 3, **the element ‘****9****’ will be compared with ‘****65****’ which is greater than ‘****9****’** so it will be **shifted one position right**, again it will be compared with ‘**54**’ and as **‘****54****’ is also greater than ‘****9****’** it will also be shifted one position right. Similarly as both ‘**32**’ and ’**12**’ is also **greater than ****9** they will also be shifted in a similar way and the array will look like below before positioning the element ‘**9**’.

After this, the element will be positioned and the final sorted array will look like this:

```
INPUT:An unsorted array arr[6,2,4,1,…………….,n]
OUTPUT:An sorted array arr[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the number of elements and the array elements in the array ]
Read n
For i=0 to n
Read arr[i]
Step 2: [Sorting the elements of the array ]
Step 2.1: For i=1 to n-1repeat Step 2.2 to Step 2.5
Step 2.2: Set t <- arr[i]
Step 2.3: For j=i-1 to 0 repeat Step 2.4
Step 2.4: If(t<arr[j]) then
Set arr[j+1] <- arr[j]
[End of ‘If’]
Else
break
[End of ‘Else’]
[End of Step 2.3 ‘For’ loop]
Step 2.5: Set arr[j+1] <- t
[End of Step 2.1 ‘For’ loop]
Step 3: [Display the sorted array]
For i=0 to n
Display (arr[i])
End For loop
Step 4: Stop
```

__CHARACTERISTICS:__

**1.** It works well for small data sets.

**2.** Insertion sort is an adaptive sorting technique.

**3.** The sorting technique is stable.

**4.** It is a comparison-based sorting technique.

**5.** It is an online sorting technique and requires a constant amount of memory spaces to be sorted.

__APPLICATION:__

**1.** It is used to sort a small set of data.

**2.** Insertion sort works very fast and well if some of the elements are already sorted.

**3.** In any other sorting technique, it can be used to sort a sub-array or sub-list to reduce the number of comparisons needed in recursion.

__ADVANTAGES:__

**1.** Works better than quick sort for small amount data.

**2.** It is an **in-place **algorithm.

**3.** Space complexity is **O(1)** which is constant and best case time complexity is **O(n)****.**

**4.** It is also called an efficient sort.

__DISADVANTAGES:__

**1.** It is not an efficient algorithm for a large number of elements.

**2.** Though the best case complexity is better than the bubble or selection sort but worse than the merge sort or quick sort.

__TIME COMPLEXITY:__

__Best case:__

The **best-case** complexity occurs if the array elements are already sorted. In case of insertion sort algorithm if the array is already sorted, for example, {1,2,3,4,5} is the array then whenever a new element is to be inserted only it is compared to its immediate left element i.e. only one comparison will be needed for each iteration.

Hence, the total number of **comparisons for n elements**:

__Average case:__

Average case complexity means that the algorithm takes the average time or steps to be completed. In case of insertion sort, the average case can be considered while it needs (n - 1)/2 comparisons in the inner loop for inserting a new element into the array i.e. while the new element will be inserted into the middle position of the sorted array.

Hence, the total number of **comparisons for n elements**:

__Worst case:__

The **worst-case** complexity occurs if the array elements are in reverse order. In that case for each ith element, the number of comparisons needed will be i - 1 i.e. for the 2nd element the number of comparisons will be 1, for the 3rd element the number of comparisons will be 2, and so on.

Hence, the total number of **comparisons for n elements**:

__SPACE COMPLEXITY:__

Related

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