What Is Insertion Sort in Data Structure?

Insertion Sort is a simple yet efficient sorting algorithm that is commonly used in the field of computer science and data structures. It is an in-place comparison-based algorithm that takes an input array and sorts it by dividing it into two parts: the sorted part and the unsorted part. The sorted part starts with only one element, and as we iterate through the unsorted part, we insert each element into its correct position in the sorted part.

How Does Insertion Sort Work?

The insertion sort algorithm works by repeatedly selecting an element from the unsorted part of the array and inserting it into its correct position in the sorted part. This process continues until the entire array is sorted.

To better understand how insertion sort works, let’s consider an example:

Input:

• 7
• 2
• 4
• 1
• 5

In the first iteration, we assume that the first element (7) is already sorted. We then compare the second element (2) with all elements in the sorted part (in this case, only one element). Since 2 is smaller than 7, we shift 7 to the right and insert 2 at its correct position.

Iteration 1:

• 2
• 7
• 4
• 1
• 5

In the second iteration, we compare the third element (4) with all elements in the sorted part (now consisting of two elements). We find that it should be placed before 7 but after 2, so we shift both 7 and 2 to the right and insert 4 at its correct position.

Iteration 2:

• 2
• 4
• 7
• 1
• 5

This process continues for the remaining elements until the entire array is sorted. In each iteration, the sorted part grows by one element.

Time Complexity of Insertion Sort

The time complexity of insertion sort is O(n^2) in the worst-case scenario, where n is the number of elements in the array. This is because, in the worst case, each element needs to be compared with all previous elements in the sorted part.

Advantages of Insertion Sort:

• Simple implementation.
• Efficient for small datasets or partially sorted arrays.

Disadvantages of Insertion Sort:

• Inefficient for large datasets or arrays that are mostly unsorted.
• The time complexity increases rapidly as the number of elements grows.

In conclusion, insertion sort is a simple and efficient sorting algorithm that is particularly useful for small datasets or partially sorted arrays. It works by gradually building up a sorted part while iterating through the unsorted part of an array. However, it may not be suitable for large datasets or arrays that are mostly unsorted due to its quadratic time complexity.