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)
• Best 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