Insertion sort functions as a straightforward sorting algorithm, resembling the manner in which you arrange playing cards in your hands. It virtually divides the array into two segments: one sorted and the other unsorted. From the unsorted portion, it selects values and positions them accurately within the sorted segment. This process keeps continuing with each iteration until the array becomes fully sorted. Additionally, this method’s efficiency improves when implemented with small datasets, making it an effective option for sorting tasks.

## Insertion Sort Algorithm

For ascending order sorting of an array with a size of N, **initially**, begin by iterating through the array. Compare the current element (referred to as the key) with the element that comes before it. If the key element happens to be smaller than its predecessor, **subsequently** proceed to compare it with the elements that precede it. In such cases, shift the larger elements one position upward **so as to** generate room for the swapped element. This series of comparisons and element shifts ensures that the array becomes sorted in ascending order.

## Working of the algorithm

Consider the following example:

**Example Array:** arr[] = {25, 18, 5, 32, 14, 7}

Pass | Array | Explanation |
---|---|---|

1st | 25 18 5 32 14 7 | The initial array |

18 25 5 32 14 7 | 25 and 18 are compared; swap them | |

18 25 5 32 14 7 | Inserted 18 into the sorted sub-array | |

2nd | 18 25 5 32 14 7 | No changes; 25 and 5 are in correct order |

18 5 25 32 14 7 | 25 and 5 are compared; swap them | |

5 18 25 32 14 7 | Inserted 5 into the sorted sub-array | |

3rd | 5 18 25 32 14 7 | No changes; 25 and 32 are already sorted |

5 18 25 32 14 7 | Inserted 32 into the sorted sub-array | |

4th | 5 18 25 32 14 7 | No changes; 25 and 14 are not in the right order |

5 18 25 14 32 7 | 32 and 14 are compared; swap them | |

5 18 25 14 32 7 | 25 and 14 are compared; swap them | |

5 18 14 25 32 7 | 25 and 14 are compared; swap them | |

5 14 18 25 32 7 | 18 and 14 are compared; swap them | |

5 14 18 25 32 7 | Inserted 14 into the sorted sub-array | |

5th | 5 14 18 25 32 7 | No changes; 25 and 7 are not in the right order |

5 14 18 25 7 32 | 32 and 7 are compared; swap them | |

5 14 18 7 25 32 | 25 and 7 are compared; swap them | |

5 14 7 18 25 32 | 18 and 7 are compared; swap them | |

5 7 14 18 25 32 | 14 and 7 are compared; swap them | |

5 7 14 18 25 32 | Inserted 7 into the sorted sub-array | |

6th | 5 7 14 18 25 32 | The array is completely sorted now |

This example illustrates the step-by-step demonstration of the insertion sort algorithm, showcasing how each pass rearranges the array into ascending order.

## Complexity Analysis

**Time Complexity of Insertion Sort**

**Worst-case**time complexity of the Insertion sort is**O(N^2)****Average case**time complexity of the Insertion sort is**O(N^2)**- B
**est case**time complexity of the Insertion sort is**O(N)**.

**Space Complexity of Insertion Sort**

The auxiliary space complexity of Insertion Sort is** O(1)**

In conclusion, the insertion sort algorithm stands as a valuable sorting technique. By systematically comparing and shifting elements, it ensures the arrangement of data in ascending order. This method’s efficiency is evident through its straightforward implementation and effectiveness, especially with smaller datasets. Consequently, insertion sort serves as a foundational sorting approach, simplifying the organization of data for a wide range of applications.

*Selection sort Read More*

## 1 thought on “Insertion Sort – Data Structure and Algorithm”