Insertion Sort
Last updated
Insertion sort builds the sorted array one element at a time. It takes the next unsorted element (the "key") and shifts every larger element in the sorted region one slot to the right, then drops the key into the gap. It is exactly how most people sort a hand of playing cards. Press play above to watch each key get inserted, or step through the shifts one at a time.
Insertion sort is very fast on small or nearly-sorted inputs - it runs in O(n) when the data is already sorted - which is why many hybrid sorts fall back to it for small subarrays.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(n) | Already sorted |
| Average case | O(n²) | Random order |
| Worst case | O(n²) | Reverse-sorted |
| Space | O(1) | In-place |
| Stable | Yes | Equal elements keep their relative order |
Step by step
| Step | What happens |
|---|---|
| 1 | Treat the first element as a sorted region of size one. |
| 2 | Take the next element as the key. |
| 3 | Shift every sorted element larger than the key one slot right. |
| 4 | Insert the key into the opened gap. |
| 5 | Repeat until every element has been inserted. |
Worked example
Sorting [5, 2, 4, 1]:
| Pass | Array | Action |
|---|---|---|
| Start | [5, 2, 4, 1] | 5 is the initial sorted region of size one. |
| 1 | [2, 5, 4, 1] | Key 2: shift 5 right, insert 2 at the front. |
| 2 | [2, 4, 5, 1] | Key 4: shift 5 right, 2 is smaller so stop, insert 4. |
| 3 | [1, 2, 4, 5] | Key 1: shift 5, 4, 2 right, insert 1 at the front. |
| Done | [1, 2, 4, 5] | Every element inserted; the array is sorted. |
When to use insertion sort
| Use it when | Avoid it when |
|---|---|
The array is small (roughly n < 20). | The array is large and randomly ordered. |
The data is already nearly sorted, giving the O(n) best case. | You need a guaranteed O(n log n) worst case. |
You need a stable, in-place sort with O(1) extra space. | Elements are expensive to move, since it does many shifts. |
| Data arrives incrementally and must stay sorted online. | The input is reverse-sorted, its O(n²) worst case. |
Insertion Sort code
A clean, runnable Insertion Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Insertion Sort code in Python
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)Insertion Sort code in JavaScript
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Insertion Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Insertion Sort code in C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}Insertion Sort code in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Insertion Sort FAQ
What is the time complexity of insertion sort?
Insertion sort is
O(n²) on average and in the worst case, but O(n) on an already-sorted or nearly-sorted array. It uses O(1) extra space.Is insertion sort stable?
Yes. Insertion sort only shifts elements that are strictly greater than the key, so equal elements never swap past each other and their relative order is preserved.
When should I use insertion sort?
Use it for small arrays or data that is already almost sorted. Because of its low overhead and adaptive best case, hybrid algorithms like Timsort use it for small runs.
What is the difference between insertion sort and bubble sort?
Both are
O(n²) comparison sorts, but insertion sort shifts elements to open a gap for the key, while bubble sort repeatedly swaps adjacent out-of-order pairs. Insertion sort usually does fewer writes and performs better in practice, especially on nearly-sorted data where it hits its O(n) best case.Why is insertion sort faster than merge sort on small arrays?
Insertion sort has very low constant-factor overhead and no recursion or extra allocation, so on small inputs it beats the
O(n log n) sorts despite its worse asymptotic complexity. This is exactly why hybrid sorts like Timsort and introsort switch to insertion sort for small subarrays.Does insertion sort work better with a linked list or an array?
Insertion sort is normally written for arrays, where shifting elements is the main cost. On a linked list you avoid the shifting by splicing the node into place, but you lose fast random access, so finding the insertion point still takes linear time per element and the overall cost stays
O(n²).Related resources
More visualizations
