Insertion Sort
Algorithm Insertion_Sort (DATA, N):
1. Repeat steps 2 to 4 for K = 2,3…N-1:
2. Set TEMP:= a[K] and J=k-1
3. Repeat while TEMP<a[J] and J>=1
a) Set a[J+1]:= a[J]. [Moves element forward]
b) Set J:=J-1
[End of loop]
4. Set a[J+1]:=TEMP. [Inserts element in proper place]
[End of step 1 Outer loop]
5. Exit
Algorithm
The simple steps of achieving the insertion sort are listed as follows -
• Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
• Step2 - Pick the next element, and store it separately in a key.
• Step3 - Now, compare the key with all elements in the sorted array.
• Step 4 - If the element in the sorted array is smaller than the current element, then
move to the next element. Else, shift greater elements in the array towards the right.
• Step 5 - Insert the value.
• Step 6 - Repeat until the array is sorted.
Program
#include <stdio.h>
int main()
int n, i, j, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
// Insertion Sort
for(i = 1; i < n; i++)
temp = a[i];
j = i - 1;
while(j >= 0 && temp < a[j])
a[j + 1] = a[j];
j = j - 1;
a[j + 1] = temp;
}
printf("Sorted array:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
Explanation with Example:
Given Array:
7, 12, 9, 11, 3
Insertion sort assumes the first element is already sorted, then inserts each next element
into its correct position.
✅ Initial Array
7 12 9 11 3
🔷 Pass 1 (i = 1)
TEMP = 12
Compare with previous element (7)
12 > 7 → No shifting needed
Array remains:
7 12 9 11 3
🔷 Pass 2 (i = 2)
TEMP = 9
Compare with 12
9 < 12 → shift 12 forward
Compare 9 with 7
9 > 7 → stop
Insert 9 at correct position.
Array becomes:
7 9 12 11 3
🔷 Pass 3 (i = 3)
TEMP = 11
Compare with 12
11 < 12 → shift 12
Compare 11 with 9
11 > 9 → stop
Insert 11.
Array becomes:
7 9 11 12 3
🔷 Pass 4 (i = 4)
TEMP = 3
Compare with 12
3 < 12 → shift
3 < 11 → shift
3 < 9 → shift
3 < 7 → shift
Insert 3 at beginning.
Final Array:
3 7 9 11 12
✅ Final Sorted Array
3 7 9 11 12
Complexity
The worst case performance occurs when the elements of the input array are in descending
order. In that case, the first pass requires 1 comparison, the 2nd pass requires 2
comparisons , and kth element requires (k-1) and finally the last pass requires (n-1)
comparisons. Therefore, total no. of comparisons in case of descending order(worst case)
is:
F(n)= 1+2+3….+(n-1)
=n(n-1)/2 = O(n2 )
Total number of comparisons in case of ascending order (best case) is: (n-1) comparisons
i.e. f(n)=O(n).
• Best Case Complexity - It occurs when there is no sorting required, i.e. the array is
already sorted. The best-case time complexity of insertion sort is O(n).
• Average Case Complexity - It occurs when the array elements are in jumbled order
that is not properly ascending and not properly descending. The average case time
complexity of insertion sort is O(n2).
• Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements in
ascending order, but its elements are in descending order. The worst-case time
complexity of insertion sort is O(n2).