Insertion Sort Algorithm
Insertion Sort is a stable, in-place comparison sorting algorithm that builds a sorted prefix one element at a time by shifting larger elements to the right.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Insertion Sort Algorithm
Insertion Sort builds the sorted array one element at a time—just like sorting playing cards in your hand. It maintains a sorted prefix on the left and repeatedly takes the next element (key), shifts any larger elements in the sorted prefix one slot to the right, and drops key into the gap.
At a Glance
| Property | Value |
| :--- | :--- |
| Best-Case Time | $O(n)$ (already sorted) |
| Average-Case Time | $O(n^2)$ |
| Worst-Case Time | $O(n^2)$ (reverse-sorted) |
| Auxiliary Space | $O(1)$ |
| In-Place? | Yes |
| Stable? | Yes (strict > keeps equal elements in original order) |
| Comparison-Based? | Yes |
| Best Used When | Small arrays ($n \le 32$), nearly sorted arrays, or online streaming inserts |
---
How It Works
1. Start at index i = 1 (the single element A[0] is trivially sorted).
2. Store key = A[i].
3. Scan backward from j = i - 1 while j >= 0 and A[j] > key, shifting A[j] to A[j + 1].
4. Place key at A[j + 1].
5. Repeat until i = n - 1.
procedure insertionSort(A):
for i = 1 to length(A) - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
Step-by-Step Trace
Sorting [9, 2, 7, 3, 6]:
- Initial:
[9 | 2, 7, 3, 6] i = 1,key = 2: Shift9right →[2, 9 | 7, 3, 6]i = 2,key = 7: Shift9right →[2, 7, 9 | 3, 6]i = 3,key = 3: Shift9, 7right →[2, 3, 7, 9 | 6]i = 4,key = 6: Shift9, 7right →[2, 3, 6, 7, 9]- Result:
[2, 3, 6, 7, 9]
---
Complexity & Key Insights
- Adaptive Time Complexity — $O(n + I)$: If the array has $I$ inversions, Insertion Sort performs exactly $I$ shifts and at most $n - 1 + I$ comparisons. On a nearly sorted array ($I = O(n)$), it runs in linear $O(n)$ time.
- Used Inside Production Sorts: Both Python/Java's Timsort and C++
std::sort's Introsort switch to Insertion Sort for small subarrays (typically $n \le 16\text{–}32$) because its low overhead and tight sequential memory access beat $O(n \log n)$ algorithms at small sizes. - Online Algorithm: It can sort elements as they arrive one by one without knowing the full dataset up front.
- When NOT to use it: On large, randomly ordered datasets ($n > 1000$), quadratic shifting dominates—switch to Merge Sort or Quick Sort.
---
Practice Problems
Easy
1. Insert an Element into a Sorted Array
Given a sorted array and a value x, insert x so that the array remains sorted.
Approach: Append x to grow the vector by one, then run a single Insertion Sort backward shift. Time: $O(n)$. Space: $O(1)$ auxiliary.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
void insertIntoSorted(std::vector<int>& arr, int x) {
arr.push_back(x);
int i = static_cast<int>(arr.size()) - 2;
while (i >= 0 && arr[i] > x) {
arr[i + 1] = arr[i];
--i;
}
arr[i + 1] = x;
}
int main() {
std::vector<int> arr = {1, 3, 5, 7};
insertIntoSorted(arr, 4);
for (int v : arr) std::cout << v << " ";
std::cout << "\n";
return 0;
}
</details>
2. Sort a Small Array
Given an array of integers, sort it in ascending order using Insertion Sort.
Approach: Standard Insertion Sort. Time: $O(n^2)$ worst / $O(n)$ best. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = static_cast<int>(arr.size());
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {9, 2, 7, 3, 6};
insertionSort(arr);
for (int v : arr) std::cout << v << " ";
std::cout << "\n";
return 0;
}
</details>
---
Intermediate
3. Count Inversions in a Nearly Sorted Array
Given an array where each element is at most $k$ positions from its sorted index, count the total number of inversions in $O(n \cdot k)$ time.
Approach: Each element shifted past key in the while loop forms an inversion with key, so counting shifts gives the exact inversion count. Time: $O(n \cdot k)$ (or $O(n^2)$ in general). Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
long long countInversions(std::vector<int> arr) {
int n = static_cast<int>(arr.size());
long long inversions = 0;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
++inversions;
}
arr[j + 1] = key;
}
return inversions;
}
int main() {
std::vector<int> arr = {2, 1, 3, 5, 4};
std::cout << "Inversions: " << countInversions(arr) << "\n";
return 0;
}
</details>
4. Sort a Singly Linked List (LeetCode 147)
Given the head of a singly linked list, sort it using Insertion Sort by relinking pointers (no data copying).
Approach: Maintain a dummy head for the sorted list. For each node cur, scan from dummy to find the insertion point where p->next->val >= cur->val and splice cur in. Time: $O(n^2)$ worst / $O(n)$ best if you check the tail first. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
struct Node {
int val;
Node* next;
explicit Node(int v) : val(v), next(nullptr) {}
};
Node* insertionSortList(Node* head) {
Node dummy(0);
Node* cur = head;
while (cur != nullptr) {
Node* next = cur->next;
Node* p = &dummy;
while (p->next != nullptr && p->next->val < cur->val) {
p = p->next;
}
cur->next = p->next;
p->next = cur;
cur = next;
}
return dummy.next;
}
void freeList(Node* head) {
while (head) {
Node* next = head->next;
delete head;
head = next;
}
}
int main() {
Node* head = new Node(4);
head->next = new Node(2);
head->next->next = new Node(5);
head->next->next->next = new Node(1);
Node* sorted = insertionSortList(head);
for (Node* p = sorted; p != nullptr; p = p->next) {
std::cout << p->val << " ";
}
std::cout << "\n";
freeList(sorted);
return 0;
}
</details>
---
Hard
5. Online Running Median for Small Streams
Maintain the running median of a stream of up to $10^4$ integers, reporting the median after every insertion.
Approach: Because Insertion Sort is an online algorithm, we can keep a sorted std::vector<int> by inserting each arriving value in $O(n)$ (and we can even use binary search to locate the insertion index in $O(\log n)$ comparisons, though shifting still takes $O(n)$). Median queries then take $O(1)$. (For streams larger than $10^4$, use two heaps for $O(\log n)$ per insertion.)
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
class RunningMedian {
std::vector<int> data;
public:
void insert(int x) {
data.push_back(x);
int i = static_cast<int>(data.size()) - 2;
while (i >= 0 && data[i] > x) {
data[i + 1] = data[i];
--i;
}
data[i + 1] = x;
}
double getMedian() const {
int n = static_cast<int>(data.size());
if (n % 2 == 1) {
return data[n / 2];
}
return (data[n / 2 - 1] + data[n / 2]) / 2.0;
}
};
int main() {
RunningMedian rm;
std::vector<int> stream = {5, 15, 1, 3};
for (int x : stream) {
rm.insert(x);
std::cout << "Median after " << x << ": " << rm.getMedian() << "\n";
}
return 0;
}
</details>
---
Related Algorithms
- Bubble Sort — similar $O(n^2)$ baseline, but slower than Insertion Sort in practice.
- Bucket Sort — often uses Insertion Sort to sort each small bucket.
- Merge Sort — scalable $O(n \log n)$ stable sort for large datasets.