Insertion Sort
Description
You are given an array of positive integers. Your task is to sort the array in ascending order using the Insertion Sort algorithm.
Insertion Sort builds the final sorted array one element at a time. It works by taking each element from the unsorted portion and inserting it into its correct position within the already-sorted portion. Think of it like sorting a hand of playing cards — you pick up one card at a time and slide it into the right spot among the cards you are already holding.
You must modify the array in-place.
Examples
Example 1
Input: arr = [4, 1, 3, 9, 7]
Output: [1, 3, 4, 7, 9]
Explanation: Starting with [4, 1, 3, 9, 7], insertion sort considers the first element (4) as already sorted. Then it takes each subsequent element and inserts it into its correct position in the sorted portion. After processing all elements, the array becomes [1, 3, 4, 7, 9].
Example 2
Input: arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explanation: This is the worst case for insertion sort — the array is in complete reverse order. Every new element must be inserted at the very beginning, requiring it to shift past all previously sorted elements. The total number of shifts is 1 + 2 + 3 + ... + 9 = 45.
Example 3
Input: arr = [4, 1, 9]
Output: [1, 4, 9]
Explanation: Element 4 is considered sorted. Element 1 is smaller than 4, so it is inserted before 4, giving [1, 4, 9]. Element 9 is already greater than all sorted elements, so it stays in place. Final array: [1, 4, 9].
Constraints
- 1 ≤ arr.size() ≤ 1000
- 1 ≤ arr[i] ≤ 10000
Editorial
Brute Force
Intuition
The simplest way to think about sorting is: for each position in the array, find the smallest element in the remaining unsorted portion and place it there. This is actually Selection Sort, and it represents the most naive comparison-based approach to sorting.
Imagine you have a messy deck of numbered cards on a table. To sort them, you scan through all the cards to find the smallest one and place it first. Then you scan the remaining cards for the next smallest and place it second. You repeat this until all cards are in order.
This approach always works, but it is inefficient because even if the array is nearly sorted, you still scan through all remaining elements to find the minimum for each position.
Step-by-Step Explanation
Let's trace through with arr = [4, 1, 3, 9, 7]:
Step 1: Find the minimum element in the entire array [4, 1, 3, 9, 7].
- Minimum is 1 at index 1.
- Swap arr[0] and arr[1].
- Array becomes: [1, 4, 3, 9, 7]
- Sorted portion: [1]
Step 2: Find the minimum in the unsorted portion [4, 3, 9, 7] (indices 1 to 4).
- Minimum is 3 at index 2.
- Swap arr[1] and arr[2].
- Array becomes: [1, 3, 4, 9, 7]
- Sorted portion: [1, 3]
Step 3: Find the minimum in the unsorted portion [4, 9, 7] (indices 2 to 4).
- Minimum is 4 at index 2.
- 4 is already at position 2 — no swap needed.
- Array stays: [1, 3, 4, 9, 7]
- Sorted portion: [1, 3, 4]
Step 4: Find the minimum in the unsorted portion [9, 7] (indices 3 to 4).
- Minimum is 7 at index 4.
- Swap arr[3] and arr[4].
- Array becomes: [1, 3, 4, 7, 9]
- Sorted portion: [1, 3, 4, 7]
Step 5: Only one element left (9) — it is already in place.
Result: [1, 3, 4, 7, 9]
Selection Sort — Find Minimum and Place It — Watch how selection sort repeatedly finds the smallest element in the unsorted portion and swaps it into its correct position at the front.
Algorithm
- For each position i from 0 to n-2:
- Scan the subarray from index i to n-1 to find the index of the minimum element
- Swap the minimum element with the element at position i
- After all positions are filled, the array is sorted
Code
class Solution {
public:
void insertSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
swap(arr[i], arr[minIdx]);
}
}
};class Solution:
def insertSort(self, arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]class Solution {
public void insertSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}Complexity Analysis
Time Complexity: O(n²)
For each of the n-1 positions, we scan through the remaining unsorted elements to find the minimum. The total comparisons are (n-1) + (n-2) + ... + 1 = n(n-1)/2. This is O(n²) in all cases — best, average, and worst — because we always scan for the minimum regardless of input order.
Space Complexity: O(1)
Only a constant number of extra variables are used (loop counters and minIdx). The sorting is done in-place.
Why This Approach Is Not Efficient
Selection sort always performs O(n²) comparisons regardless of input order. Even if the array is already sorted or nearly sorted, it still scans the entire remaining portion to find the minimum at each step.
The core inefficiency is that selection sort does not exploit existing order in the array. A nearly-sorted array gets the same treatment as a completely random one.
Insertion sort addresses this by flipping the strategy: instead of searching for the right element to place at a position, it takes the next element and finds the right position for it. Crucially, for nearly-sorted arrays, finding the right position requires very few comparisons because the element is already close to where it belongs. This gives insertion sort an O(n) best-case time complexity.
Optimal Approach - Insertion Sort
Intuition
Imagine you are holding a hand of playing cards, sorted from left to right. Someone hands you a new card. You do not rescan all your cards from the beginning — instead, you start from the right end of your hand and slide left until you find where the new card fits. You shift the larger cards to the right to make room, then insert the new card.
Insertion sort applies this exact logic to an array. We treat the first element as a sorted subarray of size 1. Then for each subsequent element (the "key"), we compare it with elements in the sorted portion from right to left. As long as the sorted element is larger than the key, we shift it one position to the right. When we find an element smaller than or equal to the key (or reach the beginning), we place the key in the gap.
The beauty of this approach is adaptive behavior: if the array is already nearly sorted, most elements are already close to their correct position, so very few shifts are needed. This makes insertion sort run in nearly O(n) time on nearly-sorted data — a dramatic improvement over selection sort's fixed O(n²).
Step-by-Step Explanation
Let's trace through with arr = [4, 1, 3, 9, 7]:
Step 1: Element arr[0] = 4 is considered sorted by itself.
- Sorted portion: [4]
- Unsorted portion: [1, 3, 9, 7]
Step 2: Pick key = arr[1] = 1. Compare with sorted portion from right.
- Compare 1 with 4: 1 < 4, so shift 4 to the right.
- Array becomes: [4, 4, 3, 9, 7] (gap at index 0)
- No more elements to compare (reached beginning).
- Place key = 1 at index 0.
- Array becomes: [1, 4, 3, 9, 7]
- Sorted portion: [1, 4]
Step 3: Pick key = arr[2] = 3. Compare with sorted portion from right.
- Compare 3 with 4: 3 < 4, so shift 4 to the right.
- Array becomes: [1, 4, 4, 9, 7] (gap at index 1)
- Compare 3 with 1: 3 > 1, stop shifting.
- Place key = 3 at index 1.
- Array becomes: [1, 3, 4, 9, 7]
- Sorted portion: [1, 3, 4]
Step 4: Pick key = arr[3] = 9. Compare with sorted portion from right.
- Compare 9 with 4: 9 > 4, no shift needed.
- key = 9 is already in its correct position.
- Array stays: [1, 3, 4, 9, 7]
- Sorted portion: [1, 3, 4, 9]
Step 5: Pick key = arr[4] = 7. Compare with sorted portion from right.
- Compare 7 with 9: 7 < 9, so shift 9 to the right.
- Array becomes: [1, 3, 4, 9, 9] (gap at index 3)
- Compare 7 with 4: 7 > 4, stop shifting.
- Place key = 7 at index 3.
- Array becomes: [1, 3, 4, 7, 9]
- Sorted portion: [1, 3, 4, 7, 9]
Result: [1, 3, 4, 7, 9]
Insertion Sort — Insert Each Element into Its Sorted Position — Watch how insertion sort picks each unsorted element and slides it leftward through the sorted portion until it finds its correct position, shifting larger elements to the right.
Algorithm
- Consider the first element as the initial sorted portion
- For each element from index 1 to n-1:
a. Store the current element askey
b. Set j = i - 1 (pointing to the last element of the sorted portion)
c. While j ≥ 0 and arr[j] > key:- Shift arr[j] one position to the right: arr[j+1] = arr[j]
- Decrement j by 1
d. Place key at position j+1 (the gap created by shifting)
- The array is now sorted
Code
class Solution {
public:
void insertSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements of the sorted portion that are
// greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
};class Solution:
def insertSort(self, arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# Shift elements of the sorted portion that are
# greater than key to one position ahead
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = keyclass Solution {
public void insertSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements of the sorted portion that are
// greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}Complexity Analysis
Time Complexity:
- Worst Case: O(n²) — When the array is in reverse sorted order, every new element must be shifted past all previously sorted elements. Total shifts: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2, which is O(n²).
- Best Case: O(n) — When the array is already sorted, each element is compared once with the last element of the sorted portion and no shifts are needed. We make exactly n-1 comparisons total — one per element.
- Average Case: O(n²) — On average, each element needs to be shifted past half of the sorted elements, giving n(n-1)/4 shifts, which is still O(n²).
The adaptive nature of insertion sort is its key advantage: the number of operations is proportional to the number of inversions (pairs of elements that are out of order) in the input.
Space Complexity: O(1)
Insertion sort is an in-place algorithm. We only use a constant amount of extra space: one variable for key and one for the loop index j. No auxiliary arrays are needed.