15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Insertion sort builds a sorted prefix from left to right. It saves the next value as a key, shifts every larger value in the prefix one place right, and drops the key into the gap. It runs in O(n) time on sorted input and O(n^2) in the worst case, uses O(1) extra space and is stable.
| Best case time | O(n), input already sorted |
|---|---|
| Average and worst case time | O(n^2), worst on reverse-sorted input |
| Extra space | O(1), sorts in place |
| Stable | Yes, when it shifts only strictly greater keys |
| Good for | Small or nearly sorted arrays |
Insertion Sort builds a sorted part of the array from left to right.
You should already be comfortable with these ideas:
0.Insertion Sort treats the first element as a sorted prefix of length one. Then it takes the next value, saves it, and inserts it into the correct position within that prefix.
Save the next value before shifting array values to make room for it.
The procedure sorts in ascending order. For equal values, it preserves their original order, which makes the algorithm stable.
Source for insertion-sort properties and analysis context: Elementary Sorts.
Use this array throughout:
1index: 0 1 2 3
2value: [3, 1, 2, 1]Start at index 0.
1[3, 1, 2, 1]The prefix containing only index 0 is already sorted:
1sorted prefix: [3]
2remaining: [1, 2, 1]Now look at index 1. Its value, 1, is the next key to insert.
The prefix [3] is sorted, and 1 belongs before 3. Overwriting index 0 with 1 would lose 3. Instead:
1 in a variable named key.3 one position right.key into the opening created at index 0.Start:
Insertion Sort on [3, 1, 2, 1]: save the next value as key, shift larger prefix values right, then drop the key into the hole. Shifting only when a[j] > key keeps the two 1s in order.
Save the value at index 1:
1key = 1
2j = 0j points to the value immediately before the key's original position.
Compare a[0] with key.
1a[0] = 3
2key = 1Since 3 > 1, shift 3 right:
1index: 0 1 2 3
2value: [3, 3, 2, 1]Index 0 is now the insertion hole. Move the backward scan left:
1j = -1The scan has reached the left boundary, so place the saved key at j + 1, which is index 0:
1index: 0 1 2 3
2value: [1, 3, 2, 1]The sorted prefix has grown:
1sorted prefix: [1, 3]
2remaining: [2, 1]The next key is at index 2.
Compare the previous value with the saved key:
1a[1] = 3
2key = 2Since 3 > 2, shift 3 right:
1index: 0 1 2 3
2value: [1, 3, 3, 1]
3
4j = 0Now compare again:
1a[0] = 1
2key = 21 > 2 is false. Stop shifting. The key belongs immediately after 1, at index j + 1 = 1.
The sorted prefix is now:
1[1, 2, 3]The final key is at index 3.
Compare 3 with 1. Since 3 > 1, shift:
1index: 0 1 2 3
2value: [1, 2, 3, 3]
3
4j = 1Compare 2 with 1. Since 2 > 1, shift:
1index: 0 1 2 3
2value: [1, 2, 2, 3]
3
4j = 0Compare 1 with 1.
1a[0] = 1
2key = 11 > 1 is false, so stop. Put the saved key at index j + 1 = 1:
1index: 0 1 2 3
2value: [1, 1, 2, 3]The array is sorted.
The final comparison uses > rather than >=. The earlier 1 stays before the later 1.
Before processing index i, everything from index 0 through index i - 1 is sorted. The value at index i is the next key to insert into that sorted prefix.
For the example, before processing index 3:
1index: 0 1 2 3
2value: [1, 2, 3, 1]
3 --------- -
4 sorted key
5 prefixThe algorithm scans backward through the sorted prefix. It shifts only values greater than the key. When the scan stops, the key goes directly after a value less than or equal to it.
The loop invariant is:
Before processing index
i, the prefixa[0..i-1]is sorted and is a permutation of the original elements from those positions; saving and insertinga[i]extends this property to indexi.
A permutation here means the prefix contains the same values as before, possibly in a different order. Shifting retains every value and moves it right by one index.
Start with the smallest sorted prefix: the first element alone.
Repeat one insertion for each later index:
key be the value currently at index i.j at index i - 1, the previous position.j is in bounds and a[j] is greater than key:
a[j] into a[j + 1].j left.key into a[j + 1].The shift condition is strict:
1a[j] > keyDo not use:
1a[j] >= keyWith the strict condition, equal previous keys are not shifted right past the saved key. Their original order remains unchanged.
For example, consider records with integer keys:
1[(2,A), (2,B)]When inserting (2,B), the previous key is 2. Since 2 > 2 is false, (2,A) is not shifted. The result remains:
1[(2,A), (2,B)]Input: mutable array a of values or records ordered by an ascending key
Return value: none
Mutation behavior: rearranges a in place into ascending order
Boundary behavior: arrays of length 0 or 1 are unchanged
Comparison contract: greater(x, y) is true exactly when x has a strictly larger sorting key than y
11 procedure insertionSort(a)
22 n ← length(a)
33
44 for i ← 1 to n - 1
55 key ← a[i]
66 j ← i - 1
77
88 while j ≥ 0 and greater(a[j], key)
99 a[j + 1] ← a[j]
1010 j ← j - 1
1111
1212 a[j + 1] ← keyLine 5 saves the key before line 9 begins overwriting array cells.
Line 8 checks j ≥ 0 before reading a[j]. If j becomes -1, there is no predecessor to inspect.
Run the pseudocode on the original input.
1index: 0 1 2 3
2a: [3, 1, 2, 1]i = 1Line 5: key ← a[1]
1key = 1Line 6: j ← i - 1
1j = 0Line 8: j ≥ 0 is true, and greater(a[0], key) means 3 > 1, which is true.
Line 9: a[1] ← a[0]
1[3, 3, 2, 1]Line 10: j ← j - 1
1j = -1Line 8: j ≥ 0 is false. Exit the while loop.
Line 12: a[j + 1] ← key, so a[0] ← 1
1[1, 3, 2, 1]i = 2Line 5: key ← a[2]
1key = 2Line 6: j ← i - 1
1j = 1Line 8: j ≥ 0 is true, and 3 > 2 is true.
Line 9: a[2] ← a[1]
1[1, 3, 3, 1]Line 10:
1j = 0Line 8: j ≥ 0 is true, and 1 > 2 is false. Exit the while loop.
Line 12: a[1] ← 2
1[1, 2, 3, 1]i = 3Line 5: key ← a[3]
1key = 1Line 6: j ← i - 1
1j = 2Line 8: j ≥ 0 is true, and 3 > 1 is true.
Line 9: a[3] ← a[2]
1[1, 2, 3, 3]Line 10:
1j = 1Line 8: j ≥ 0 is true, and 2 > 1 is true.
Line 9: a[2] ← a[1]
1[1, 2, 2, 3]Line 10:
1j = 0Line 8: j ≥ 0 is true, and 1 > 1 is false. Exit the while loop.
Line 12: a[1] ← 1
1[1, 1, 2, 3]The for loop has processed every index from 1 through 3, so it ends.
We prove that the procedure sorts the array, keeps the same elements, and preserves the order of equal-key records.
Before the first outer iteration, i = 1.
The prefix a[0..0] contains one element. A one-element sequence is sorted. It also contains exactly the original element from position 0.
The invariant is true before any insertion happens.
Assume that before processing index i, the prefix a[0..i-1] is sorted and contains exactly the original elements from positions 0 through i-1.
The algorithm saves a[i] as key.
The inner loop shifts each prefix value greater than key one position to the right. Each shift copies a value and retains it. The shifts create one available position, the insertion hole.
The loop stops in one of two situations:
j = -1, so every value in the prefix was greater than key. The key goes at index 0.a[j] is less than or equal to key. The key goes at index j + 1.In either situation:
key.key.a[0..i] is sorted.The prefix also contains the same original values from positions 0 through i: every shifted value remains present, and the saved key is inserted exactly once.
One outer iteration preserves the invariant for the next index.
The outer loop ends after processing index n - 1, where n is the array length.
At that point, the invariant says that a[0..n-1], the entire array, is sorted and is a permutation of the original array.
Therefore, Insertion Sort correctly sorts the array.
Consider an earlier record and a later record with equal keys.
The inner loop shifts a previous record only when:
1previous key > saved keyIf their keys are equal, the condition is false. The earlier record remains before the later saved record. Equal-key records remain in their original relative order.
The version of Insertion Sort shown here is stable.
The outer loop processes indices 1 through n - 1.
The work inside an iteration depends on how far the key moves left.
In a descending array, every new key moves all the way to the front.
For the key at index i, the algorithm can compare and shift across i earlier positions.
The total is:
11 + 2 + 3 + ... + (n - 1)That sum is quadratic in n, so the worst-case time is:
1O(n^2)For example, reverse-sorted input [3,2,1] causes the key 2 to shift once and the key 1 to shift twice.
In an already sorted array such as [1,2,3], each key is already after a value less than or equal to it.
Each outer iteration performs one failed comparison and no shifts.
There are n - 1 outer iterations, so the best-case time is:
1O(n)Insertion Sort adapts to already sorted input because it performs no shifts when each next key is already in position.
The algorithm uses:
key,i,j,n.These are constant-sized variables beyond the input array.
1Auxiliary space: O(1)The array itself is rearranged in place.
Incorrect approach:
1a[i] ← a[j]without first saving:
1key ← a[i]Smallest exposing input:
1[3, 1]If the code shifts 3 into index 1 before saving 1:
1[3, 3]The value 1 is lost. There is no way to restore it.
Correction:
1key ← a[i]must happen before the first shift.
>= while claiming stabilityIncorrect loop condition:
1while j ≥ 0 and a[j].key ≥ key.keySmallest exposing input:
1[(2,A), (2,B)]When inserting (2,B), the incorrect condition treats the earlier (2,A) as something to shift:
1[(2,A), (2,A)]Then (2,B) is inserted at the front:
1[(2,B), (2,A)]The records are sorted by key, and their equal-key order changed. The sort is no longer stable.
Correction:
1while j ≥ 0 and a[j].key > key.keyShift only strictly greater keys.
Incorrect approach:
1for i ← 0 to n - 1
2 j ← i - 1
3 compare a[j] with keySmallest exposing input:
1[5]At i = 0:
1j = -1Reading a[-1] is invalid predecessor access.
Correction:
1.j ≥ 0 as the first condition of the inner loop.1for i ← 1 to n - 1
2 while j ≥ 0 and greater(a[j], key)1[] → []
2[4] → [4]
3[1,2,3] → [1,2,3] // no shifts
4[3,2,1] → [1,2,3] // each key moves to the front
5[2,1,2] → [1,2,2]For stability, use records rather than plain integers:
1[(2,A), (2,B)] → [(2,A), (2,B)]Implement stable ascending Insertion Sort for records with integer keys.
Your implementation contract:
Executable tests verify:
1def insertion_sort(a):
2 for i in range(1, len(a)):
3 key = a[i] # save the key before any shift
4 j = i - 1
5 while j >= 0 and a[j] > key: # strictly greater keeps it stable
6 a[j + 1] = a[j]
7 j -= 1
8 a[j + 1] = key
9
10nums = [3, 1, 2, 1]
11insertion_sort(nums)
12print(nums)1import java.util.Arrays;
2
3public class Main {
4 static void insertionSort(int[] a) {
5 for (int i = 1; i < a.length; i++) {
6 int key = a[i]; // save the key before any shift
7 int j = i - 1;
8 while (j >= 0 && a[j] > key) { // strictly greater keeps it stable
9 a[j + 1] = a[j];
10 j--;
11 }
12 a[j + 1] = key;
13 }
14 }
15
16 public static void main(String[] args) {
17 int[] nums = {3, 1, 2, 1};
18 insertionSort(nums);
19 System.out.println(Arrays.toString(nums));
20 }
21}1#include <iostream>
2#include <vector>
3using namespace std;
4
5void insertionSort(vector<int>& a) {
6 for (int i = 1; i < (int)a.size(); i++) {
7 int key = a[i]; // save the key before any shift
8 int j = i - 1;
9 while (j >= 0 && a[j] > key) { // strictly greater keeps it stable
10 a[j + 1] = a[j];
11 j--;
12 }
13 a[j + 1] = key;
14 }
15}
16
17int main() {
18 vector<int> nums = {3, 1, 2, 1};
19 insertionSort(nums);
20 cout << "[";
21 for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i];
22 cout << "]" << endl;
23}1function insertionSort(a) {
2 for (let i = 1; i < a.length; i++) {
3 const key = a[i]; // save the key before any shift
4 let j = i - 1;
5 while (j >= 0 && a[j] > key) { // strictly greater keeps it stable
6 a[j + 1] = a[j];
7 j--;
8 }
9 a[j + 1] = key;
10 }
11}
12
13const nums = [3, 1, 2, 1];
14insertionSort(nums);
15console.log(`[${nums.join(', ')}]`);Take [3, 1, 2, 1]. Save 1, shift 3 right and place 1 first: [1, 3, 2, 1]. Save 2, shift 3, place it: [1, 2, 3, 1]. Save the last 1, shift 3 and 2, and it stops behind the first 1: [1, 1, 2, 3].
No. On an already sorted array each key needs one comparison and no shifts, so the whole sort is O(n). The O(n^2) bound is the worst case, reached on reverse-sorted input where every key moves to the front.
Selection sort scans the unsorted part for its minimum and swaps it into place, so it always does about n^2/2 comparisons. Insertion sort moves the next value back through the sorted part and stops early, so it is O(n) on sorted input. The insertion sort shown here is stable; standard selection sort is not.
The inner loop shifts a value only when it is strictly greater than the key. An equal value stays put, so the key lands after it and records with equal keys keep their original order. Changing the test to >= breaks this.
Use it for small arrays or data that is already nearly sorted, where few keys move far. Library sorts such as Timsort switch to insertion sort for short runs for this reason.