Insertion Sort
Legend
- • Numbers show element values
- • Bottom labels show array indices
- • Colors indicate current operation
- • Height represents value magnitude
Inspector
Legend
- • Numbers show element values
- • Bottom labels show array indices
- • Colors indicate current operation
- • Height represents value magnitude
Inspector
Reference implementation of Insertion Sort. Select a language tab to view and copy the code.
void insertion_sort(int arr[], int n) {
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;
}
}#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;
}
}public static void insertionSort(int[] arr) {
int n = arr.length;
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;
}
}def insertion_sort(arr: list[int]) -> None:
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = keyfunction insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}Python — Code Walkthrough
range starts at 1
for i in range(1, len(arr))A one-element prefix [arr[0]] is trivially sorted. range(1, len(arr)) iterates i = 1, 2, … n−1, extending the sorted prefix by one element each pass.
key saves the value
key = arr[i]Python integers are immutable values; assigning key = arr[i] creates an independent copy. This is important because arr[i] will be overwritten in the shifting loop.
j walks left
j = i - 1j starts just left of the current element and decrements while the while condition is true.
Shift and decrement
while j >= 0 and arr[j] > key: arr[j + 1] = arr[j]; j -= 1Python's and short-circuits: j >= 0 is evaluated first, so arr[j] is never read at a negative index. Each iteration copies arr[j] one slot to the right.
Insert after the loop
arr[j + 1] = keyWhen the loop exits, j+1 is the correct insertion point. Python does not need a temp variable here — key was saved upfront.