**Insertion Sort-**

- Insertion sort is an in-place sorting algorithm.
- It uses no auxiliary data structures while sorting.
- It is inspired from the way in which we sort playing cards.

**How Insertion Sort Works?**

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

Insertion sort works as-

Firstly,

- It selects the second element (2).
- It checks whether it is smaller than any of the elements before it.
- Since 2 < 6, so it shifts 6 towards right and places 2 before it.
- The resulting list is 2, 6, 11, 7, 5.

Secondly,

- It selects the third element (11).
- It checks whether it is smaller than any of the elements before it.
- Since 11 > (2, 6), so no shifting takes place.
- The resulting list remains the same.

Thirdly,

- It selects the fourth element (7).
- It checks whether it is smaller than any of the elements before it.
- Since 7 < 11, so it shifts 11 towards right and places 7 before it.
- The resulting list is 2, 6, 7, 11, 5.

Fourthly,

- It selects the fifth element (5).
- It checks whether it is smaller than any of the elements before it.
- Since 5 < (6, 7, 11), so it shifts (6, 7, 11) towards right and places 5 before them.
- The resulting list is 2, 5, 6, 7, 11.

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

**Also Read-** **Selection Sort**

**Insertion Sort Algorithm-**

Let A be an array with n elements. The insertion sort algorithm used for sorting is as follows-

for (i = 1 ; i < n ; i++) { Ā Ā key = A [ i ]; Ā Ā j = i - 1; Ā Ā while(j > 0 && A [ j ] > key) Ā Ā { Ā Ā Ā Ā A [ j+1 ] = A [ j ]; Ā Ā Ā Ā j--; Ā Ā } Ā Ā A [ j+1 ] = key; }

Here,

- i = variable to traverse the array A
- key = variable to store the new number to be inserted into the sorted sub-array
- j = variable to traverse the sorted sub-array

**Insertion Sort Example-**

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above insertion sort algorithm works as illustrated below-

**Step-01: For i = 1**

**Step-02: For i = 2**

**Step-03: For i = 3**

2 | 5 | 11 | 7 | 6 | For j = 2; 11 > 7 so A[3] = 11 | |

2 | 5 | 11 | 11 | 6 | For j = 1; 5 < 7 so loop stops and A[2] = 7 | |

2 | 5 | 7 | 11 | 6 | After inner loop ends |

Working of inner loop when i = 3

**Step-04: For i = 4**

Loop gets terminated as ‘i’ becomes 5. The state of array after the loops are finished-

With each loop cycle,

- One element is placed at the correct location in the sorted sub-array until array A is completely sorted.

**Time Complexity Analysis-**

- Selection sort algorithm consists of two nested loops.
- Owing to the two nested loops, it has O(n
^{2}) time complexity.

Time Complexity | |

Best Case | n |

Average Case | n^{2} |

Worst Case | n^{2} |

**Space Complexity Analysis-**

- Selection sort is an in-place algorithm.
- It performs all computation in the original array and no other array is used.
- Hence, the space complexity works out to be O(1).

**Important Notes-**

- Insertion sort is not a very efficient algorithm when data sets are large.
- This is indicated by the average and worst case complexities.
- Insertion sort is adaptive and number of comparisons are less if array is partially sorted.

To gain better understanding about Insertion Sort Algorithm,

**Next Article-** **Quick Sort**

Get more notes and other study material of **Design and Analysis of Algorithms.**

Watch video lectures by visiting our YouTube channel **LearnVidFun**.