How it works
Maintain a sorted portion on the left. Pick the next key element, then shift larger elements right until you find the correct insertion point.
The Pattern
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] // shift right
j--
arr[j+1] = key // insert
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] // shift right
j--
arr[j+1] = key // insert
Interactive Visualization
Key Element Shifting Sorted Region Placed
Array
Bar Chart
Step 0 of 0
Key
—
Comparisons
0
Shifts
0
Inserted
0
Ready. Press Play or Next to start.
✓ Sorted
Speed
C++ — Insertion Sort
void insertionSort(vector<int>& arr) { for (int i = 1; i < arr.size(); i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // shift right j--; } arr[j + 1] = key; // insert } }
Complexity
Time (Worst)
O(N²)
Reverse sorted array, max shifts.
Time (Best)
O(N)
Already sorted, no shifts needed.
Space
O(1)
In-place sort.
Stable?
Yes
Equal elements keep order.