Insertion Sort Algorithm
Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.
Insertion sort works similarly as we sort cards in our hand in a card game.
We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.
A similar approach is used by insertion sort.
Working of Insertion Sort
Insertion Sort builds the sorted array one element at a time, by comparing each new element with the already sorted part and inserting it in the correct position.
Step-by-Step Working:
- Start from the second element, assuming the first element is already sorted.
- Compare the current element with the elements in the sorted part (to its left).
- Shift all larger elements in the sorted part one position to the right.
- Insert the current element into its correct position in the sorted part.
- Repeat steps 2 to 4 for all remaining elements in the array.
- After the last pass, the entire array will be sorted.
Example Given Array:
[9, 5, 1, 4, 3]
Pass 1:
- Key = 5
- Compare with 9 → 5 < 9 → Shift 9
- Insert 5 →
[5, 9, 1, 4, 3]
Pass 2:
- Key = 1
- Compare with 9, 5 → Shift both
- Insert 1 at beginning
[1, 5, 9, 4, 3]
Pass 3:
- Key = 4
- Compare with 9, 5 → Shift both
- Insert 4
[1, 4, 5, 9, 3]
Pass 4:
- Key = 3
- Compare with 9, 5, 4 → Shift all
- Insert 3
[1, 3, 4, 5, 9]
Sorted Array:
[1, 3, 4, 5, 9]
Insertion sort Python code:
for i = 1 to n-1:
key = arr[i]
j = i – 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j – 1
arr[j+1] = key
Time Complexity of Insertion Sort:
|
Case |
Time Complexity |
Explanation |
|
Best Case |
O(n) |
When the array is already sorted. Only n-1 comparisons, no shifting needed. |
|
Average Case |
O(n²) |
Random order elements; shifting needed in about half of the comparisons. |
|
Worst Case |
O(n²) |
When the array is in reverse order; each element must be compared and shifted. |
Space Complexity:
- O (1) (in-place sorting, uses no extra space)
Note:
Insertion Sort is efficient for small or nearly sorted datasets and is adaptive, unlike Selection Sort. It is also stable, meaning it maintains the relative order of equal elements.