What is Insertion Sort in Data Structure? | Data Structure Tutorial

In this article, you will learn about the insertion sort algorithm in the data structure in brief.

The insertion algorithm is used to place an unsorted element at its suitable position in each iteration. It works very similarly to the sort of cards in the hand in a card game. 

Insertion Sort Algorithm

1. We assume that the first element in the list is already sorted. Now take the second element and store it separately in the key. Do compare with the first element. If the first element has a higher value, then the key is placed in front of the first element. 
2. Afterward, the first two elements are sorted. Go to the third element and compare it with the elements on the left-hand side of it. Keep it just behind the smaller element than it. If there is no element smaller than the key, then place it at the beginning of the array. 
3. In a similar way, place every unsorted element in its correct place.

Insortion_sort(array)

   mark the first element as sorted

   for each unsorted element I

      ‘extract’ the element I

      for j <- lastSortedIndex down to 0

         if current element j > I

           move a sorted element to the right by 1

       break the loop and insert I 

end Insertion_sort

Complexity

Time complexity

The best case complexity is O(n), the average case complexity is O(n2), and the worst case complexity is O(n2). 

The space complexity is O(1). 

Occurrence of each complexity

1. Best case complexity: If the array is sorted, then the outer loop runs for n number of times however, the inner loop does not run at all. So, only n number of comparisons. Thus, complexity is linear. 
2. Average case complexity: It happens when the elements of a list are in a puzzled order.
3. Worst case complexity: It happens when a list is in ascending order, and you want to sort it in descending order. 

Applications of Insertion Sort

• It is used if the number of elements in the array is very small. 
• It is used only when we need to sort a few elements in an array.