insertionSort.definition
insertionSort.descriptionPart1
insertionSort.descriptionPart2
insertionSort.keyPointsTitle
- insertionSort.keyPoint1
- insertionSort.keyPoint2
- insertionSort.keyPoint3
- insertionSort.keyPoint4
insertionSort.exampleTitle
Start:
524613
i=1:
254613
i=2:
245613
Sorted:
123456
insertionSort.syntaxTitle
// Java
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;
}
}# Python
def insertion_sort(arr):
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] = key// C++
void insertionSort(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;
}
}// JavaScript
function insertionSort(arr) {
for (let i = 1; i < arr.length; 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;
}
return arr;
}Interactive Insertion Sort Visualization
📊
Enter numbers above and click "Create Array" to begin.
Current Index: 0Comparisons: 0Shifts: 0Elements: 0
Idle
Key
Comparing
Shifting
Sorted
Note: Insertion Sort picks a key element and inserts it into the sorted portion by shifting larger elements to the right. It is efficient for small or nearly sorted arrays.
Time & Space Complexity
| Case | Complexity | Description |
|---|---|---|
| Best Case | O(n) | Array is already sorted (only n-1 comparisons needed) |
| Average Case | O(n²) | Random order requires many shifts and comparisons |
| Worst Case | O(n²) | Array is sorted in reverse order (maximum shifts) |
| Space | O(1) | In-place sorting, only uses a few variables |
Comparisons: In the worst case, Insertion Sort makes n(n-1)/2 comparisons.
Shifts: In the worst case, it performs n(n-1)/2 shifts (element moves).
Stability: Insertion Sort is a stable sorting algorithm (equal elements maintain their relative order).
Adaptive: Efficient for data sets that are already substantially sorted.
insertionSort.continueLearning
enhanced.author.title
enhanced.author.writtenBy:enhanced.author.teamName
enhanced.author.reviewedBy:enhanced.author.reviewerName
enhanced.author.lastUpdated:January 29, 2026