Insertion Sort
Let us understand this algorithm with an analogy
This algorithm works like organizing cards in your hand during a card game.
Imagine you start with one card, which is considered sorted by itself since there are no other cards to compare it. Therefore, the first element is assumed to be sorted.
Then, you pick the next card from the deck. You compare it with the cards in your hand and find the right spot. If the new card is smaller than the cards you already have, you shift those cards to the right to make room and insert the new card in its correct place.
You keep repeating this process for each card, always placing it where it belongs among the sorted cards you’ve already arranged. By the end, all your cards are sorted.
Similarly, in insertion sort, each element is picked from the unsorted part and placed into its correct position within the sorted portion, gradually sorting the entire array.
Let us understand a step-by-step working of Insertion Sort with an example :
Suppose we have the following array of integers nums: [5, 2, 9, 1, 5, 6] that we want to sort in ascending order:
Step-by-Step Working
Initial nums: [5, 2, 9, 1, 5, 6]
Since we have discussed that the first element is assumed to be sorted, let's proceed to sort the remaining unsorted portion of the array
So let’s assume that we have divided the array nums into two parts: Sorted portion, and unsorted portion.
Where the sorted portion will contain the element from the index 1 to i-1 and the unsorted portion will contain the element from the index i to n.
Pass 1
Inserting the Second Element ( i = 2 )
- Sorted portion: [5]
- Unsorted portion: [2, 9, 1, 5, 6]
- Key: 2
- Comparison: Compare 2 with 5.
- Since 2 is less than 5, shift 5 to the right.
- nums after shifting: [5, 5, 9, 1, 5, 6]
- Insert 2 at the correct position.
nums after Pass 1: [2, 5, 9, 1, 5, 6]
Pass 2
Inserting the Third Element ( i = 3 )
- Sorted portion: [2, 5]
- Unsorted portion: [9, 1, 5, 6]
- Key: 9
- Comparison: Compare 9 with 5.
- Since 9 is greater than 5, 9 stays in place.
nums after Pass 2: [2, 5, 9, 1, 5, 6]
Pass 3
Inserting the Fourth Element ( i = 4 )
- Sorted portion: [2, 5, 9]
- Unsorted portion: [1, 5, 6]
- Key: 1
- Comparison:
- Compare 1 with 9. Since 1 is less, shift 9 to the right.
- Compare 1 with 5. Since 1 is less, shift 5 to the right.
- Compare 1 with 2. Since 1 is less, shift 2 to the right.
- nums after shifting: [2, 2, 5, 9, 5, 6]
- Insert 1 at the beginning.
- nums after Pass 3: [1, 2, 5, 9, 5, 6]
Pass 4
Inserting the Fifth Element ( i = 5 )
- Sorted portion: [1, 2, 5, 9]
- Unsorted portion: [5, 6]
- Key: 5
- Comparison: Compare 5 with 9.
- Since 5 is less than 9, shift 9 to the right.
- nums after shifting: [1, 2, 5, 9, 9, 6]
- Insert 5 before 9.
- nums after Pass 4: [1, 2, 5, 5, 9, 6]
Pass 5
Inserting the Sixth Element ( i = 6 )
- Sorted portion: [1, 2, 5, 5, 9]
- Unsorted portion: [6]
- Key: 6
- Comparison: Compare 6 with 9.
- Since 6 is less than 9, shift 9 to the right.
- nums after shifting: [1, 2, 5, 5, 9, 9]
- Insert 6 before 9.
- nums after Pass 5: [1, 2, 5, 5, 6, 9]
Final Sorted nums : [1, 2, 5, 5, 6, 9]
Let's understand it through visuals
Here is the code of Insertion sort in all languages:
Code in All Languages
C++ Code Try on Compiler!
class Solution
{
public:
void insertionSort(vector<int> &nums)
{
int n = nums.size();
for (int i = 1; i < n; i++)
{
// The element to be inserted
int key = nums[i];
// Index of the previous element
int j = i - 1;
// Move elements of nums[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && nums[j] > key)
{
nums[j + 1] = nums[j];
j--;
}
// Insert the key at the correct position
nums[j + 1] = key;
}
}
};Java Code Try on Compiler!
class Solution {
void insertionSort(int[] nums) {
int n = nums.length;
// Traverse from the second element to the last
for (int i = 1; i < n; i++) {
// Store the current element
int key = nums[i];
int j = i - 1;
// Shift elements of the sorted portion to the right
// until the correct position for the key is found
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
// Insert the key at its correct position
nums[j + 1] = key;
}
}
}Python Code Try on Compiler!
class Solution:
def insertion_sort(nums):
# Traverse from the second element to the last
for i in range(1, len(nums)):
# Store the current element
key = nums[i]
j = i - 1
# Move elements of the sorted portion that are greater than the key
# one position to the right
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
# Place the key at its correct position
nums[j + 1] = keyJavascript Code Try on Compiler!
class Solution {
insertionSort(nums) {
// Traverse from the second element to the last
for (let i = 1; i < nums.length; i++) {
// Store the current element
let key = nums[i];
let j = i - 1;
// Move elements of the sorted portion that are greater than the key
// one position to the right
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
// Place the key at its correct position
nums[j + 1] = key;
}
}
}Time Complexity
Worst Case : O(n²)
This occurs when the array is sorted in reverse order. In this case, each element must be compared with all previously sorted elements and shifted to its correct position.
The number of Comparisons and Shifts:
For an array with n elements:
- First Element: No comparisons (already considered sorted).
- Second Element: 1 comparison (with the first element).
- Third Element: Up to 2 comparisons (with the first two elements).
- Fourth Element: Up to 3 comparisons, and so forth.
- Total Comparisons: The total number of comparisons made is the sum of the first n−1 natural numbers, which is given by the formula (n*(n-1))/2.
- Total Comparisons: Simplifying, this results in approximately (n²)/2, which is O(n²).
Number of Shifts: Each comparison may require a shift if the element is out of order. The number of shifts is also proportional to the number of comparisons, leading to O(n²) in the average and worst cases.
Overall Time Complexity: Because both the number of comparisons and shifts are proportional to (n*(n-1))/2, the overall time complexity worst case is O(n²).
Average Case : O(n²)
This occurs when the elements of the array are in random order. On average, each element needs to be compared with a portion of the elements that are already sorted. Since the arrangement of elements is random, the exact number of comparisons required can vary.
However, in general, the number of comparisons and shifts needed tends to be quadratic in relation to the number of elements.
Therefore, the time complexity for the average case is still O(n²).
Best Case : O(n)
In the best case for insertion sort, the array is already sorted. Here, the algorithm operates with maximum efficiency.
Each element is already in its correct position relative to the elements before it. During the sorting process, the algorithm only needs to compare each element with the one directly preceding it, confirming that no further action is required.
Since no elements need to be shifted, the algorithm performs only one comparison per element. Consequently, with n elements in the array, the time complexity is O(n).
This linear time complexity reflects the algorithm's optimal performance when dealing with an already sorted array.
Space Complexity
Insertion sort has a constant space complexity of O(1). It only requires a small, fixed amount of extra space for the key and temporary variables used during the sorting process, regardless of the size of the input array.
Thus, Insertion Sort is considered an in-place sorting algorithm, meaning it sorts the array without needing extra space proportional to the number of elements.
Stability Of Algorithm
Yes, insertion sort is a stable sorting algorithm.
Explanation: Stability in sorting means that if two elements are equal, their relative order will be preserved in the sorted array. Insertion sort maintains the relative order of equal elements because it only inserts the current element into its correct position and does not alter the order of equal elements that are already in place.
Application of Insertion Sort
It is favored for small or nearly sorted data, adaptive sorting, and as part of hybrid sorting algorithms due to its efficiency in those contexts.