What is Insertion sort algorithm in data structure

What is Insertion Sort?

Insertion Sort is a comparison-based sorting algorithm that builds the final sorted array one item at a time. In this sorting algorithm, we divide the array into two parts:
1. Sorted Subarray
2. Unsorted Subarray
This Algorithm is the most simple algorithm to sort an array. Initially, the sorted subarray contains only the first element then we pick 1st element from the unsorted subarray. Put it into temp. And then compare that temp value with the sorted array. If a temp value is greater than the last element of the sorted array then just move that shell into the sorted array and if it’s smaller than the last element then move that element to the next place and compare with the second last element. Do this process until and unless you find the right place for the temp value.

How Does Insertion Sort Work?

To learn the process of insertion sorting, we are taking a given example: A[] = {5 , 3 , 7 , 10 , 34 , 9 , 1}.

Step 1:

In insertion sort, we sort from left to right. So the most left element(0th element) is considered a sorted element. and after that, all elements will be considered into an unsorted array. Please check Fig. 1.

Step 2:

Now, to compare the unsorted element with the sorted element insert the first element of the unsorted array into the temp variable then that shell will be empty. And now, compare it with the most last element sorted array.

Step 3:

Here, two conditions come into the picture. First, if the Temp value is greater than last element of the sorted array then just move that element into a sorted array as it is. Or if the Temp value is less than the last element of sorted array. Then shift right to that last element where the Temp value was stored.

Step 4:

Store the temp value in the sorted array.

Step 5:

Now in the second iteration, we have 2 elements in a sorted array. and 3rd one(7) is in temp. Now perform step number 2 and 3. So, 7 is greater than 5 then we will just move 7 into the sorted array. Please check FIg. 2 for more clarity.

Step 6:

Now, 10 will be into the temp variable. and we will perform step number 2 and 3 again. Likewise, we are going to perform steps 2 and 3 until and unless we get a sorted array. Please check FIg. 2 and Fig. 3 for more clarity.

Best Practices for Using Insertion Sort

To make the most of Insertion Sort and optimize its performance, consider the following best practices:

Know the Data:
Understand the characteristics of your data before selecting Insertion Sort. It excels in scenarios like small input sizes or partially sorted arrays.

Benchmark and Compare:
Analyze the expected input size and compare the performance of Insertion Sort with other sorting algorithms. Choose the most appropriate algorithm based on your specific requirements.

Consider Optimization Techniques:
Apply optimization techniques such as early termination or adaptive variations of Insertion Sort to enhance its efficiency for particular cases.

Combine with Other Algorithms:
Insertion Sort can be used as a preliminary step in conjunction with more advanced sorting algorithms. For example, using Insertion Sort to partially sort the array before applying a more efficient algorithm can yield better results.

Conclusion - Insertion sort algorithm in data structure

In the above article, we learned about what is insertion sort, It is a significant sorting method that makes sorting tiny input sizes or incompletely sorted arrays simple.