Imagine you're playing cards. The dealer hands you one card at a time, and you keep the cards in your hand sorted.
Every time you get a new card, you don't re-sort the whole hand. You simply slide the new card left until it sits in the right place.
Hand: [3, 7, 9]
New card: 5
Slide 5 left past 9, past 7, stop at 3
Hand: [3, 5, 7, 9]That's exactly how Insertion Sort works.
Insertion Sort builds the sorted array one element at a time by taking the next element and inserting it into its correct position among the elements that are already sorted.
Insertion Sort is simple like Bubble Sort and Selection Sort, but it has some special strengths: it is very fast on nearly sorted data, it is stable, and real-world sorting libraries still use it for small arrays.
The Core Idea
Insertion Sort divides the array into two parts:
[ sorted part | unsorted part ]At the start, the sorted part contains only the first element. A single element is always sorted.
[5 | 2, 4, 6, 1, 3]
↑
sortedThen, one by one, we pick the first element of the unsorted part (called the key) and insert it into the correct position in the sorted part.
Pick key
↓
Compare it with elements on its left
↓
Shift every bigger element one step right
↓
Drop the key into the gap
↓
Sorted part grows by oneAfter processing every element, the whole array is sorted.
Shifting, Not Swapping
This is the detail that makes Insertion Sort efficient.
Suppose the sorted part is [2, 4, 5, 6] and the key is 1.
We first save the key in a variable:
key = 1
[2, 4, 5, 6, 1]Then we shift every element bigger than the key one position to the right:
6 > 1 → shift [2, 4, 5, 6, 6]
5 > 1 → shift [2, 4, 5, 5, 6]
4 > 1 → shift [2, 4, 4, 5, 6]
2 > 1 → shift [2, 2, 4, 5, 6]We have reached the beginning of the array, so we place the key in the gap:
[1, 2, 4, 5, 6]The duplicates you see in the middle are temporary. Because we saved the key first, nothing is lost.
Each shift is one assignment, while a swap needs three. That's why the standard version shifts instead of swapping.
Step-by-Step Example
Let's sort:
[5, 2, 4, 6, 1, 3]Pass 1 (key = 2)
Sorted part: [5]
5 > 2 → shift 5 right
Reached the start → insert 2
[2, 5, 4, 6, 1, 3]Pass 2 (key = 4)
Sorted part: [2, 5]
5 > 4 → shift 5 right
2 < 4 → stop, insert 4 after 2
[2, 4, 5, 6, 1, 3]Pass 3 (key = 6)
Sorted part: [2, 4, 5]
5 < 6 → stop immediately (no shifts)
[2, 4, 5, 6, 1, 3]Notice that when the key is already bigger than everything before it, the pass costs just one comparison.
Pass 4 (key = 1)
Sorted part: [2, 4, 5, 6]
6, 5, 4, 2 are all bigger → shift all four
Reached the start → insert 1
[1, 2, 4, 5, 6, 3]Pass 5 (key = 3)
Sorted part: [1, 2, 4, 5, 6]
6 > 3 → shift
5 > 3 → shift
4 > 3 → shift
2 < 3 → stop, insert 3 after 2
[1, 2, 3, 4, 5, 6]The array is sorted after n - 1 = 5 passes.
Insertion Sort in Java
Here's the complete program. It also prints the array after every pass so you can match it with the trace above.
import java.util.Arrays;
class Main {
static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift bigger elements one position to the right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Drop the key into the gap
arr[j + 1] = key;
System.out.println("After pass " + i + ": "
+ Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 4, 6, 1, 3};
System.out.println("Original: "
+ Arrays.toString(arr));
insertionSort(arr);
System.out.println("Sorted: "
+ Arrays.toString(arr));
}
}Output:
Original: [5, 2, 4, 6, 1, 3]
After pass 1: [2, 5, 4, 6, 1, 3]
After pass 2: [2, 4, 5, 6, 1, 3]
After pass 3: [2, 4, 5, 6, 1, 3]
After pass 4: [1, 2, 4, 5, 6, 3]
After pass 5: [1, 2, 3, 4, 5, 6]
Sorted: [1, 2, 3, 4, 5, 6]Understanding the Code
The outer loop starts at index 1, not 0:
for (int i = 1; i < n; i++)because the first element alone is already a sorted part.
We save the current element before anything overwrites it:
int key = arr[i];The inner loop walks left through the sorted part:
while (j >= 0 && arr[j] > key)It stops for one of two reasons:
j < 0 → we passed the start of the array
arr[j] <= key → we found an element that is not biggerIn both cases, the correct position for the key is j + 1:
arr[j + 1] = key;The loop invariant is worth remembering for interviews:
At the start of each pass i, the subarray arr[0..i-1] contains the original first i elements, in sorted order.
Time Complexity
The amount of work depends heavily on how the input is arranged. Let's count the actual comparisons and shifts for three arrays of size 8:
class Main {
static void countWork(String label, int[] arr) {
int comparisons = 0;
int shifts = 0;
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0) {
comparisons++;
if (arr[j] > key) {
arr[j + 1] = arr[j];
shifts++;
j--;
} else {
break;
}
}
arr[j + 1] = key;
}
System.out.println(label + " -> comparisons = "
+ comparisons + ", shifts = " + shifts);
}
public static void main(String[] args) {
countWork("Sorted ", new int[]{1, 2, 3, 4, 5, 6, 7, 8});
countWork("Random ", new int[]{3, 7, 1, 8, 2, 6, 4, 5});
countWork("Reversed ", new int[]{8, 7, 6, 5, 4, 3, 2, 1});
}
}Output:
Sorted -> comparisons = 7, shifts = 0
Random -> comparisons = 19, shifts = 13
Reversed -> comparisons = 28, shifts = 28Best Case: Already Sorted
Every key is already bigger than the element before it, so each pass does exactly one comparison and zero shifts.
Comparisons = n - 1 = 7
Time = O(n)Worst Case: Reverse Sorted
Every key is smaller than everything before it, so it travels all the way to the front.
Comparisons = 1 + 2 + ... + (n - 1)
= n(n - 1) / 2
= 8 × 7 / 2 = 28
Time = O(n²)Average Case
On random data, a key moves about halfway back on average, which is still about n² / 4 comparisons:
Time = O(n²)Shifts = Inversions
Here's a neat fact. An inversion is a pair of positions (i, j) with i < j but arr[i] > arr[j], a pair that is "out of order".
Each shift fixes exactly one inversion. So:
The number of shifts Insertion Sort performs equals the number of inversions in the array.
The random array [3, 7, 1, 8, 2, 6, 4, 5] has 13 inversions, which is exactly the 13 shifts in the output above. A nearly sorted array has very few inversions, so Insertion Sort finishes in almost linear time.
Space Complexity
We only use a few variables (key, i, j), so:
Space = O(1) (in-place)Case | Time | When it happens |
|---|---|---|
Best |
| Already sorted |
Average |
| Random order |
Worst |
| Reverse sorted |
Space |
| Always |
Insertion Sort Is Stable
A sorting algorithm is stable if elements with equal keys keep their original relative order.
Insertion Sort is stable because the inner loop uses a strict comparison:
arr[j] > keyAn element equal to the key is never shifted past it.
Let's sort students by marks. Riya and Dev both have 72, and Aman and Kabir both have 85:
class Main {
static void insertionSortByMarks(String[] names, int[] marks) {
for (int i = 1; i < marks.length; i++) {
int keyMarks = marks[i];
String keyName = names[i];
int j = i - 1;
// Strictly greater: equal marks are NOT moved
while (j >= 0 && marks[j] > keyMarks) {
marks[j + 1] = marks[j];
names[j + 1] = names[j];
j--;
}
marks[j + 1] = keyMarks;
names[j + 1] = keyName;
}
}
public static void main(String[] args) {
String[] names = {"Aman", "Riya", "Kabir", "Sneha", "Dev"};
int[] marks = { 85, 72, 85, 60, 72 };
insertionSortByMarks(names, marks);
for (int i = 0; i < names.length; i++) {
System.out.println(names[i] + " " + marks[i]);
}
}
}Output:
Sneha 60
Riya 72
Dev 72
Aman 85
Kabir 85Riya still comes before Dev, and Aman still comes before Kabir, just like in the original input.
If you change > to >=, the array is still sorted, but equal elements get reversed and the sort is no longer stable.
Other Useful Properties
Adaptive
An algorithm is adaptive if it runs faster when the input is already partly sorted. Insertion Sort is a perfect example: its running time is O(n + inversions).
Online
Insertion Sort is online: it can sort data as it arrives, without seeing the whole input first. Each new element is simply inserted into the already sorted part, just like picking up cards one at a time.
Used Inside Real Sorting Libraries
For very small arrays, Insertion Sort beats O(n log n) algorithms because it has almost no overhead. That's why hybrid algorithms use it for small pieces:
Java's
Arrays.sort()for objects uses TimSort, which uses (binary) insertion sort to build short sorted runs.Java's
Arrays.sort()for primitives uses Dual-Pivot Quicksort, which switches to insertion sort for tiny subarrays.Python's built-in
sorted()also uses insertion sort for short runs.
Binary Insertion Sort
Since the left part is always sorted, we could use Binary Search to find where the key belongs, instead of comparing one by one.
Comparisons per pass → O(log n) (instead of O(n))However, we still have to shift all the bigger elements to make room. In the worst case, that's still O(n) shifts per pass.
Total time → still O(n²)Binary insertion sort helps when comparisons are expensive (for example, comparing long strings or complex objects), but it does not change the overall Big O.
Common Mistakes
1. Wrong order of conditions in the while loop
// Wrong: arr[-1] is accessed when j becomes -1
while (arr[j] > key && j >= 0)
// Correct: check the index first
while (j >= 0 && arr[j] > key)Java's && is short-circuit, so checking j >= 0 first prevents an ArrayIndexOutOfBoundsException.
2. Not saving the key
If you write arr[j + 1] = arr[j] without saving arr[i] first, the first shift overwrites the key and its value is lost.
3. Placing the key at arr[j] instead of arr[j + 1]
When the loop ends, j points to the element that is not bigger than the key (or to -1). The gap is one step to its right.
4. Using >= instead of >
The result is still sorted, but the sort becomes unstable and does extra shifts for duplicates.
5. Starting the outer loop at 0
It works, but the first pass does nothing useful. Start at 1.
Insertion vs Bubble vs Selection
All three are simple O(n²) algorithms, but they behave differently:
Property | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|
Best case |
|
|
|
Average / Worst |
|
|
|
Space |
|
|
|
Stable | Yes | No (standard version) | Yes |
Writes to array | Many swaps | At most | One write per shift |
Adaptive | Yes (with flag) | No | Yes |
In practice, Insertion Sort is usually the fastest of the three. Selection Sort is only preferred when writing to memory is very expensive, because it does the fewest swaps.
When Should You Use Insertion Sort?
Good choices:
Small arrays (roughly a few dozen elements)
Nearly sorted arrays
Data arriving one element at a time (online sorting)
When you need a stable, in-place sort with simple code
As the "small case" inside a faster hybrid sort
Bad choices:
Large random or reverse-sorted arrays, where
O(n²)becomes too slow. Use Merge Sort or Quick Sort (coming up next) instead.
Interview Tips and Practice
Questions interviewers like to ask:
Why is Insertion Sort O(n) on sorted input? Because each pass stops after one comparison.
How many shifts does it do? Exactly the number of inversions.
Why do libraries still use it? It has tiny overhead, so it is fastest for small or nearly sorted inputs.
Does binary search make it O(n log n)? No, shifting is still
O(n²)in the worst case.
Practice problems:
Insertion Sort List (LeetCode 147): apply the same idea to a linked list, after you learn Linked Lists.
Sort an array of 0s, 1s and 2s using insertion sort, then compare with better approaches.
Count the number of inversions in an array using insertion sort (you'll learn a faster way in Merge Sort).
Sort a "k-sorted" array, where every element is at most
kpositions away from its final place. Insertion Sort solves it inO(n·k).
The Main Idea
Insertion Sort keeps a sorted part on the left and inserts each new element into its correct place by shifting bigger elements to the right.
Pick key
↓
Shift bigger elements right
↓
Insert key into the gap
↓
Repeat for every elementIts key facts:
Best → O(n) (already sorted)
Average → O(n²)
Worst → O(n²) (reverse sorted)
Space → O(1)
Stable → Yes
Adaptive and Online → YesInsertion Sort is the best simple sorting algorithm for small or nearly sorted data, which is why even modern hybrid sorts rely on it for small pieces of the array.
In the next chapter, we'll see Merge Sort, which breaks the O(n²) barrier by splitting the problem in half again and again.