Insertion Sort
In this page:
Basic Idea
Insertion sort builds a sorted portion at the front of the array one element at a time, taking the next unsorted element and shifting it backward through the sorted portion until it lands in its correct position — much like sorting playing cards in your hand.
Example: Basic Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
for (int i = 1; i < arr.length; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
System.out.println(Arrays.toString(arr));
}
}arr = [5, 1, 4, 2, 8]
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
print(arr)#include <stdio.h>
int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
For each new element, the algorithm compares it against sorted elements from right to left, shifting larger ones one position to the right, until it finds the spot where the new element belongs and inserts it there.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
cout << "Inserting " << key << " into sorted part" << endl;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2};
for (int i = 1; i < arr.length; i++) {
int key = arr[i], j = i - 1;
System.out.println("Inserting " + key + " into sorted part");
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
}
}arr = [5, 1, 4, 2]
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
print("Inserting", key, "into sorted part")
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key#include <stdio.h>
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
printf("Inserting %d into sorted part\n", key);
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Tracing insertion sort on a small, mostly-sorted array like [3, 1, 2] shows how few shifts are actually needed when the input is close to sorted already, versus a reverse-sorted array where nearly every insertion shifts the whole sorted portion.
Example: Small Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
for (int k = 0; k < n; k++) cout << arr[k] << " ";
cout << endl;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2};
for (int i = 1; i < arr.length; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
System.out.println(java.util.Arrays.toString(arr));
}
}
}arr = [5, 1, 4, 2]
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
print(arr)#include <stdio.h>
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
for (int k = 0; k < n; k++) printf("%d ", arr[k]);
printf("\n");
}
return 0;
}Login to try C/C++/Java code in the editor
Practice
Try comparing insertion sort's behavior on an already-sorted array against a reverse-sorted one of the same size — the sorted case does almost no shifting at all, which is the property that makes insertion sort genuinely fast on nearly-sorted data.
Example: Practice
#include <iostream>
using namespace std;
int main() {
int arr[] = {9, 3, 7, 1};
int n = 4, shifts = 0;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; }
arr[j + 1] = key;
}
cout << "Total shifts: " << shifts;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1};
int shifts = 0;
for (int i = 1; i < arr.length; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; }
arr[j + 1] = key;
}
System.out.println("Total shifts: " + shifts);
}
}arr = [9, 3, 7, 1]
shifts = 0
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
shifts += 1
arr[j + 1] = key
print("Total shifts:", shifts)#include <stdio.h>
int main() {
int arr[] = {9, 3, 7, 1};
int n = 4, shifts = 0;
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; }
arr[j + 1] = key;
}
printf("Total shifts: %d", shifts);
return 0;
}Login to try C/C++/Java code in the editor
Summary
Insertion sort's worst case is O(n²), same as bubble and selection sort, but its best case on already-sorted input is O(n), making it a practical choice for small or nearly-sorted arrays despite the same worst-case complexity class as the others.
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data");
}
}print("Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data")#include <stdio.h>
int main() {
printf("Insertion sort: O(n^2) worst case but fast and adaptive on nearly-sorted data");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: