Insertion Sort
What Is Insertion Sort?
Insertion sort works exactly like sorting a hand of playing cards. You pick up one card at a time and insert it into the correct position among the cards already in your hand.
Sorting cards in hand: [3, 7, 1, 5, 2] Start with: [3] hand sorted Pick up 7: [3, 7] 7 ≥ 3 → insert at end Pick up 1: [1, 3, 7] 1 < 7 → shift 7; 1 < 3 → shift 3; insert 1 at front Pick up 5: [1, 3, 5, 7] 5 < 7 → shift 7; 5 ≥ 3 → insert before 7 Pick up 2: [1, 2, 3, 5, 7] 2 < 5 → shift; 2 < 3 → shift; 2 ≥ 1 → insert At every point, the left portion is sorted. Each new element finds its place by shifting larger elements rightward.
The left portion grows by one element per pass. Each pass inserts the next element from the unsorted right portion into its correct position in the sorted left portion.
Basic Insertion Sort
1public class InsertionSort {
2
3 public static void insertionSort(int[] arr) {
4 int n = arr.length;
5
6 for (int i = 1; i < n; i++) {
7 int key = arr[i]; // Element to be inserted
8 int j = i - 1; // Start comparing from the end of sorted portion
9
10 // Shift elements greater than key one position to the right
11 while (j >= 0 && arr[j] > key) {
12 arr[j + 1] = arr[j]; // Shift right — NOT a swap
13 j--;
14 }
15
16 // Insert key at its correct position
17 arr[j + 1] = key;
18 }
19 }
20
21 public static void main(String[] args) {
22 int[] arr1 = {12, 11, 13, 5, 6};
23 insertionSort(arr1);
24 System.out.println(java.util.Arrays.toString(arr1));
25 // [5, 6, 11, 12, 13]
26
27 int[] arr2 = {5, 1, 4, 2, 8};
28 insertionSort(arr2);
29 System.out.println(java.util.Arrays.toString(arr2));
30 // [1, 2, 4, 5, 8]
31
32 // Best case — already sorted
33 int[] sorted = {1, 2, 3, 4, 5};
34 insertionSort(sorted);
35 System.out.println(java.util.Arrays.toString(sorted));
36 // [1, 2, 3, 4, 5]
37
38 // Worst case — reverse sorted
39 int[] reversed = {5, 4, 3, 2, 1};
40 insertionSort(reversed);
41 System.out.println(java.util.Arrays.toString(reversed));
42 // [1, 2, 3, 4, 5]
43 }
44}Output:
[5, 6, 11, 12, 13]
[1, 2, 4, 5, 8]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
Complete Dry Run: [12, 11, 13, 5, 6]
Tracing every insertion — showing shift operations (not swaps) and the growing sorted prefix:
arr = [12, 11, 13, 5, 6] n=5 i=1, key=11: j=0: arr[0]=12 > 11 → shift: arr[1]=12 [12, 12, 13, 5, 6] j=-1: loop ends arr[0] = key=11 [11, 12, 13, 5, 6] sorted prefix: [11, 12] i=2, key=13: j=1: arr[1]=12 > 13? No → loop ends immediately arr[2] = key=13 (already in place) [11, 12, 13, 5, 6] sorted prefix: [11, 12, 13] i=3, key=5: j=2: arr[2]=13 > 5 → shift: arr[3]=13 [11, 12, 13, 13, 6] j=1: arr[1]=12 > 5 → shift: arr[2]=12 [11, 12, 12, 13, 6] j=0: arr[0]=11 > 5 → shift: arr[1]=11 [11, 11, 12, 13, 6] j=-1: loop ends arr[0] = key=5 [5, 11, 12, 13, 6] sorted prefix: [5, 11, 12, 13] i=4, key=6: j=3: arr[3]=13 > 6 → shift: arr[4]=13 [5, 11, 12, 13, 13] j=2: arr[2]=12 > 6 → shift: arr[3]=12 [5, 11, 12, 12, 13] j=1: arr[1]=11 > 6 → shift: arr[2]=11 [5, 11, 11, 12, 13] j=0: arr[0]=5 > 6? No → loop ends arr[1] = key=6 [5, 6, 11, 12, 13] sorted prefix: [5, 6, 11, 12, 13] Sorted: [5, 6, 11, 12, 13] ✓ Total shifts: 7 Total comparisons: 8 Note: SHIFTS not swaps — each shift is one assignment, not three (no temp variable needed)
Shifts vs Swaps — Why It Matters
Insertion sort does shifts (single assignments), not swaps (three assignments). This is one reason it performs better than bubble sort in practice.
SWAP (3 assignments): temp = arr[j] ← write 1 arr[j] = arr[j+1] ← write 2 arr[j+1] = temp ← write 3 SHIFT (1 assignment): arr[j+1] = arr[j] ← write 1 (key is saved separately before the loop starts) For n=5 array requiring 7 shifts: Bubble sort (swaps): 7 × 3 = 21 assignments Insertion sort (shifts): 7 × 1 + 1 (final insert) = 8 assignments For large n with many inversions: insertion sort does ~3× fewer memory writes.
Best Case, Worst Case, Average Case Explained
BEST CASE — Already sorted: [1, 2, 3, 4, 5] i=1, key=2: arr[0]=1 > 2? No → 1 comparison, 0 shifts i=2, key=3: arr[1]=2 > 3? No → 1 comparison, 0 shifts i=3, key=4: arr[2]=3 > 4? No → 1 comparison, 0 shifts i=4, key=5: arr[3]=4 > 5? No → 1 comparison, 0 shifts Total: n-1 = 4 comparisons, 0 shifts → O(n) ✓ WORST CASE — Reverse sorted: [5, 4, 3, 2, 1] i=1, key=4: shift 5 past (1 shift) i=2, key=3: shift 5,4 past (2 shifts) i=3, key=2: shift 5,4,3 past (3 shifts) i=4, key=1: shift 5,4,3,2 past (4 shifts) Total: 1+2+3+4 = n(n-1)/2 = 10 shifts → O(n²) AVERAGE CASE — Random input Element at position i has been placed in a random position relative to the sorted prefix. On average it needs i/2 shifts. Total: Σ i/2 for i=1..n-1 = n(n-1)/4 ≈ O(n²) KEY INSIGHT: the number of shifts equals the number of inversions. An inversion is a pair (i,j) where i < j but arr[i] > arr[j]. Sorted array: 0 inversions → O(n) shifts Reverse sorted: n(n-1)/2 inversions → O(n²) shifts Nearly sorted: few inversions → nearly O(n)
Why Insertion Sort Is Stable
The inner while loop condition is arr[j] > key — strictly greater than. When equal elements are encountered (arr[j] == key), the condition is false — the loop stops and key is inserted after the equal element. Equal elements are never moved past each other.
Input: [(A,3), (B,3), (C,1), (D,3)] sort by number i=1, key=(B,3): j=0: arr[0]=(A,3).val=3 > 3? No → loop ends arr[1] = (B,3) stays in place [A(3), B(3), C(1), D(3)] i=2, key=(C,1): j=1: (B,3).val=3 > 1 → shift [A(3), B(3), B(3), D(3)] j=0: (A,3).val=3 > 1 → shift [A(3), A(3), B(3), D(3)] j=-1: loop ends arr[0] = (C,1) [C(1), A(3), B(3), D(3)] i=3, key=(D,3): j=2: (B,3).val=3 > 3? No → loop ends arr[3] = (D,3) stays in place [C(1), A(3), B(3), D(3)] Final: [C(1), A(3), B(3), D(3)] A still before B before D — original order of equal-3 elements preserved ✓ STABLE SORT CONFIRMED.
Variant: Binary Insertion Sort
Use binary search to find the insertion position — reduces comparisons from O(i) to O(log i) per element.
Total comparisons: O(n log n) instead of O(n²). Total shifts: Still O(n²) — binary search finds where to insert but doesn't reduce how many elements must shift.
1import java.util.Arrays;
2
3public class BinaryInsertionSort {
4
5 // Binary search: find leftmost position where arr[pos] >= key
6 private static int findInsertPos(int[] arr, int lo, int hi, int key) {
7 while (lo < hi) {
8 int mid = lo + (hi - lo) / 2;
9 if (arr[mid] > key) hi = mid;
10 else lo = mid + 1;
11 }
12 return lo;
13 }
14
15 public static void binaryInsertionSort(int[] arr) {
16 for (int i = 1; i < arr.length; i++) {
17 int key = arr[i];
18 int pos = findInsertPos(arr, 0, i, key); // O(log i) comparisons
19
20 // Shift elements from pos to i-1 one position right — O(i) shifts
21 int j = i;
22 while (j > pos) {
23 arr[j] = arr[j - 1];
24 j--;
25 }
26
27 arr[pos] = key;
28 }
29 }
30
31 public static void main(String[] args) {
32 int[] arr = {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54};
33 binaryInsertionSort(arr);
34 System.out.println(Arrays.toString(arr));
35 // [0, 12, 17, 23, 31, 37, 46, 54, 72, 88, 100]
36 }
37}Output:
[0, 12, 17, 23, 31, 37, 46, 54, 72, 88, 100]
Insertion Sort on a Linked List
For a linked list, insertion sort avoids the shift cost — instead of shifting elements, you relink pointers. Each insert is O(1) pointer operations once the position is found.
1public class InsertionSortLinkedList {
2
3 static class ListNode {
4 int val; ListNode next;
5 ListNode(int v) { val = v; next = null; }
6 }
7
8 public static ListNode insertionSortList(ListNode head) {
9 ListNode dummy = new ListNode(0); // Sorted list starts empty
10
11 ListNode curr = head;
12 while (curr != null) {
13 ListNode next = curr.next;
14
15 // Find position in sorted list where curr belongs
16 ListNode prev = dummy;
17 while (prev.next != null && prev.next.val < curr.val) {
18 prev = prev.next;
19 }
20
21 // Insert curr between prev and prev.next
22 curr.next = prev.next;
23 prev.next = curr;
24
25 curr = next; // Advance to next unsorted node
26 }
27
28 return dummy.next;
29 }
30
31 private static String listToString(ListNode head) {
32 StringBuilder sb = new StringBuilder("[");
33 while (head != null) {
34 sb.append(head.val);
35 if (head.next != null) sb.append(", ");
36 head = head.next;
37 }
38 return sb.append("]").toString();
39 }
40
41 public static void main(String[] args) {
42 // Build [4, 2, 1, 3]
43 ListNode head = new ListNode(4);
44 head.next = new ListNode(2);
45 head.next.next = new ListNode(1);
46 head.next.next.next = new ListNode(3);
47
48 System.out.println("Before: " + listToString(head));
49 ListNode sorted = insertionSortList(head);
50 System.out.println("After: " + listToString(sorted));
51 // After: [1, 2, 3, 4]
52 }
53}Output:
Before: [4, 2, 1, 3]
After: [1, 2, 3, 4]
Where Insertion Sort Is Used in Practice
TimSort (Python, Java, JavaScript built-in sort): TimSort identifies natural sorted runs in the array. For runs shorter than 64 elements, it uses insertion sort. Reason: for small n, insertion sort's low overhead and excellent cache locality outperform merge sort's O(n log n) with its recursive calls and auxiliary array allocation. IntroSort (C++ std::sort): Hybrid of quicksort, heapsort, and insertion sort. Uses insertion sort when the subarray size drops below ~16 elements. Same reasoning: minimal overhead for tiny subarrays. Nearly-sorted data: Database results that are "almost sorted" after a re-query. Insertion sort: O(n + k) where k is the number of inversions. For k = O(n), this is O(n) — much faster than O(n log n) sorts. Online sorting / streaming data: New data arrives one element at a time. Insertion sort maintains a sorted array, inserting each arrival O(n). Total for n arrivals: O(n²) — but practical because it sorts in-place as data arrives without buffering all data first.
Three Simple Sorts Compared
Property Insertion Sort Bubble Sort Selection Sort ────────────────────────────────────────────────────────────────────── Best case O(n) ← WINNER O(n) O(n²) Average case O(n²) O(n²) O(n²) Worst case O(n²) O(n²) O(n²) Comparisons best n-1 n-1 n(n-1)/2 Shifts/Swaps best 0 0 0 Shifts/Swaps worst n(n-1)/2 shifts n(n-1)/2 swaps n-1 swaps Stable ✓ Yes ✓ Yes ✗ No Adaptive ✓ Yes ← WINNER ✓ Yes ✗ No In-place ✓ O(1) ✓ O(1) ✓ O(1) Online ✓ Yes ← WINNER ✗ No ✗ No Write efficiency Shifts (1 write) Swaps (3 writes) ≤ n-1 swaps ← WINNER Used in practice ✓ TimSort, IntroSort ✗ Never ✗ Only write-limited hw
Insertion sort wins for nearly-sorted, small arrays, online data, and as a subroutine in hybrid sorts. Selection sort wins only when write count is critical. Bubble sort loses to insertion sort on all practical metrics — insertion sort should be preferred.
Complexity Summary
| Case | Comparisons | Shifts | Time | Space | Stable |
|---|---|---|---|---|---|
| Best (sorted) | n-1 | 0 | O(n) | O(1) | ✓ Yes |
| Average | n(n-1)/4 | n(n-1)/4 | O(n²) | O(1) | ✓ Yes |
| Worst (reverse) | n(n-1)/2 | n(n-1)/2 | O(n²) | O(1) | ✓ Yes |
| Binary insertion | O(n log n) | O(n²) | O(n²) | O(1) | ✓ Yes |
| Linked list | O(n²) comparisons | O(1) per insert (pointer relink) | O(n²) | O(1) | ✓ Yes |
Common Mistakes
Using >= instead of > in the while condition. The condition must be arr[j] > key (strictly greater). Using >= shifts equal elements past key, making the sort unstable. With >, equal elements stop the shift immediately — key is inserted after all equal elements.
Initialising j = i instead of j = i - 1. The key is extracted from arr[i]. The inner loop compares elements in the sorted prefix arr[0..i-1]. Starting at j = i would compare arr[i] with itself (already extracted as key), causing an off-by-one.
Not saving key = arr[i] before the shift loop. The shift loop overwrites arr[j+1] = arr[j]. If the first shift position is j = i-1, then arr[i] = arr[i-1] — the value at index i is now overwritten. The key must be saved in a separate variable before any shifting begins.
Forgetting j >= 0 in the while condition. Without this bound check, j reaches -1 and arr[-1] is an out-of-bounds access. In C++/Java this causes undefined behaviour or an exception. The condition must be j >= 0 && arr[j] > key.
Interview Questions
Q: How does insertion sort's O(n) best case work and when is it useful?
For an already-sorted array, each element in the outer loop (position i) is compared to its predecessor at arr[i-1]. Since arr[i-1] ≤ arr[i], the while loop condition is immediately false — 0 shifts, 1 comparison. Total: n-1 comparisons, O(n). This is useful for re-sorting data that receives small updates — insert the changed element into the otherwise-sorted array in O(n) time, much faster than re-sorting from scratch in O(n log n).
Q: Why does binary insertion sort not improve the overall O(n²) complexity?
Binary search reduces the comparison count per element from O(i) to O(log i), making total comparisons O(n log n). However, the total work is dominated by shifts: once the insertion position is found, all elements between that position and i must shift one position right. This costs O(i) assignments regardless of how efficiently the position was found. For n elements, total shifts remain O(n²). Overall complexity: O(n²).
Q: Why do TimSort and IntroSort use insertion sort internally for small subarrays?
For small n (typically n < 16-64), the constant factors matter more than asymptotic complexity. Insertion sort's inner loop is a simple shift with excellent cache locality. Merge sort's overhead — recursive calls, stack frames, and auxiliary array allocation — exceeds the savings from O(n log n) for small n. In practice, the threshold is chosen empirically: below it, insertion sort is faster; above it, merge/quicksort wins.
FAQs
How many inversions does an array have and what is the connection to insertion sort?
An inversion is a pair (i, j) where i < j but arr[i] > arr[j] — elements that are "out of order." The number of shifts insertion sort makes equals exactly the number of inversions. A sorted array has 0 inversions (0 shifts). A reverse-sorted array of n elements has n(n-1)/2 inversions (maximum shifts). Nearly-sorted data has few inversions, making insertion sort nearly O(n) for such inputs.
Is insertion sort faster than bubble sort for random input?
Yes — consistently. Both are O(n²) but insertion sort's constant factor is smaller. Each "swap" in bubble sort requires 3 assignments (via a temp variable). Each "shift" in insertion sort requires 1 assignment (the key is pre-saved). For n=1000 random elements, insertion sort typically runs 2-3× faster than bubble sort in benchmarks. This is why TimSort and IntroSort use insertion sort — not bubble sort — as their small-array subroutine.
Can insertion sort be parallelised?
Not naturally. Each step depends on the result of the previous insertion — the sorted prefix must be complete before the next element is inserted. There are parallel variants (e.g., odd-even insertion sort) that process multiple elements simultaneously on SIMD hardware, but standard insertion sort is fundamentally sequential. For parallel sorting, merge sort or radix sort are better starting points.
Summary
Insertion sort grows a sorted prefix one element at a time by taking the next unsorted element (key) and shifting larger elements rightward until the correct insertion position is found.
The implementation in three lines of logic:
for i in 1..n-1:
key = arr[i]
shift arr[j] right while j >= 0 AND arr[j] > key
arr[j+1] = key
Key properties:
- ›Stable —
>not>=; equal elements never shifted past each other - ›Adaptive — O(n) for sorted input; O(n + k) for k inversions
- ›In-place — O(1) extra space (just the
keyvariable) - ›Online — can insert streaming elements one at a time
- ›Shifts, not swaps — 3× fewer memory writes than bubble sort
Variants:
- ›Binary insertion sort — O(n log n) comparisons, O(n²) shifts — useful when comparisons are expensive
- ›Linked list insertion — O(1) per insert (pointer relink), O(n²) overall — avoids the shift cost
- ›Used in TimSort / IntroSort — insertion sort handles small subarrays (n < 16-64) where its low overhead beats O(n log n) sorts
When to choose:
- ›Nearly-sorted data — dramatically fewer shifts
- ›Small n (< ~50) — lower constant factor than merge/quick sort
- ›Online/streaming — insert each arriving element in O(n)
- ›Stable sort needed with O(1) space
In the next topic, you will explore Merge Sort — the O(n log n) divide-and-conquer sort that is guaranteed stable and fast, and is the backbone of TimSort and external sorting.
What is the best-case time complexity of insertion sort and when does it occur?