{"title":"Insertion Sort","description":"","content":"Insertion Sort builds a sorted array one element at a time, much like sorting playing cards in a hand. It is efficient for small datasets and nearly sorted arrays where only a few shifts are needed.\n\nIt is not suitable for large inputs, but it remains worth understanding because of its simplicity, stability, and practical performance in hybrid algorithms.\n\n\n\n\n\nThis chapter covers how Insertion Sort works, how to implement it, and the scenarios where it outperforms more complex algorithms.\n\n---\n\n# What Is Insertion Sort?\n\nInsertion Sort builds a sorted portion of the array one element at a time. It picks the next unsorted element and inserts it into its correct position within the already-sorted region.\n\nAt any point during the algorithm, the array is divided into two regions:\n\n- **Sorted region (left side):** All elements here are in their final relative order.\n- **Unsorted region (right side):** These elements have not been processed yet.\n\nThe algorithm repeatedly takes the first element from the unsorted region and places it where it belongs in the sorted region, shifting larger elements to the right to make room.\n\n\n```mermaid\nflowchart LR\n subgraph SORTED[\"Sorted Region\"]\n A[\"1\"]\n B[\"3\"]\n C[\"5\"]\n end\n\n subgraph UNSORTED[\"Unsorted Region\"]\n D[\"2\"]:::teal\n E[\"9\"]\n F[\"7\"]\n end\n\n D -- \"Insert into
correct position\" --> SORTED\n\n style A fill:#69db7c,stroke:#000,color:#000\n style B fill:#69db7c,stroke:#000,color:#000\n style C fill:#69db7c,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#ffa94d,stroke:#000,color:#000\n style F fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nThe algorithm is straightforward: take each element, compare it to what is already sorted, and place it in the right position. No auxiliary data structures are required.\n\n---\n\n# How It Works\n\nThe algorithm has six steps:\n\n1. Start with the second element (index 1). The first element by itself is already \"sorted.\"\n2. Save the current element in a temporary variable called `key`.\n3. Compare `key` with each element in the sorted region, moving from right to left.\n4. Shift every element that is larger than `key` one position to the right.\n5. Place `key` into the gap created by the shifts.\n6. Move to the next unsorted element and repeat until the entire array is sorted.\n\nThe standard implementation shifts elements rather than swapping them. An alternative approach uses adjacent swaps, but shifting elements to the right in a single pass and then placing the key in its final position is more efficient: each shift is a single assignment, while a swap requires three assignments (using a temporary variable).\n\n\n```mermaid\nflowchart TD\n START[\"Start: i = 1\"] --> SAVE[\"Save key = arr[i]\"]\n SAVE --> SETJ[\"Set j = i - 1\"]\n SETJ --> CHECK{\"j >= 0 AND
arr[j] > key?\"}\n CHECK -- \"Yes\" --> SHIFT[\"Shift: arr[j+1] = arr[j]
Decrement j\"]\n SHIFT --> CHECK\n CHECK -- \"No\" --> PLACE[\"Place: arr[j+1] = key\"]\n PLACE --> NEXT{\"i < n - 1?\"}\n NEXT -- \"Yes\" --> INC[\"Increment i\"]\n INC --> SAVE\n NEXT -- \"No\" --> DONE[\"Array is sorted\"]\n\n style START fill:#00ceff,stroke:#000,color:#000\n style SAVE fill:#ffa94d,stroke:#000,color:#000\n style SETJ fill:#ffa94d,stroke:#000,color:#000\n style CHECK fill:#38d9a9,stroke:#000,color:#000\n style SHIFT fill:#ff8787,stroke:#000,color:#000\n style PLACE fill:#69db7c,stroke:#000,color:#000\n style NEXT fill:#38d9a9,stroke:#000,color:#000\n style INC fill:#00ceff,stroke:#000,color:#000\n style DONE fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe inner while loop shifts elements to the right as long as they are greater than the key. It stops at the first element that is smaller than or equal to the key, and the key drops into the gap right after that element. Insertion Sort is stable because the loop shifts only elements that are strictly greater than the key, which preserves the original relative order of equal elements.\n\n---\n\n# Code Implementation\n\n\n```java\npublic static void insertionSort(int[] arr) {\n int n = arr.length;\n\n for (int i = 1; i < n; i++) {\n int key = arr[i];\n int j = i - 1;\n\n // Shift elements that are greater than key to the right\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n\n // Place key in its correct position\n arr[j + 1] = key;\n }\n}\n```\n\n```python\ndef insertion_sort(arr):\n n = len(arr)\n\n for i in range(1, n):\n key = arr[i]\n j = i - 1\n\n # Shift elements that are greater than key to the right\n while j >= 0 and arr[j] > key:\n arr[j + 1] = arr[j]\n j -= 1\n\n # Place key in its correct position\n arr[j + 1] = key\n```\n\n```cpp\nvoid insertionSort(vector& arr) {\n int n = arr.size();\n\n for (int i = 1; i < n; i++) {\n int key = arr[i];\n int j = i - 1;\n\n // Shift elements that are greater than key to the right\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n\n // Place key in its correct position\n arr[j + 1] = key;\n }\n}\n```\n\n```go\npackage main\n\n// insertionSort sorts the array in ascending order using insertion sort.\nfunc insertionSort(arr []int) {\n\tn := len(arr)\n\n\tfor i := 1; i < n; i++ {\n\t\tkey := arr[i]\n\t\tj := i - 1\n\n\t\t// Shift elements that are greater than key to the right\n\t\tfor j >= 0 && arr[j] > key {\n\t\t\tarr[j+1] = arr[j]\n\t\t\tj--\n\t\t}\n\n\t\t// Place key in its correct position\n\t\tarr[j+1] = key\n\t}\n}\n```\n\n```csharp\npublic static void InsertionSort(int[] arr) {\n int n = arr.Length;\n\n for (int i = 1; i < n; i++) {\n int key = arr[i];\n int j = i - 1;\n\n // Shift elements that are greater than key to the right\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n\n // Place key in its correct position\n arr[j + 1] = key;\n }\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn insertion_sort(arr: &mut Vec) {\n let n = arr.len();\n\n for i in 1..n {\n let key = arr[i];\n let mut j = i as i32 - 1;\n\n // Shift elements that are greater than key to the right\n while j >= 0 && arr[j as usize] > key {\n arr[(j + 1) as usize] = arr[j as usize];\n j -= 1;\n }\n\n // Place key in its correct position\n arr[(j + 1) as usize] = key;\n }\n }\n}\n```\n\n```javascript\nfunction insertionSort(arr) {\n const n = arr.length;\n\n for (let i = 1; i < n; i++) {\n const key = arr[i];\n let j = i - 1;\n\n // Shift elements that are greater than key to the right\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n\n // Place key in its correct position\n arr[j + 1] = key;\n }\n}\n```\n\n```typescript\nfunction insertionSort(arr: number[]): void {\n const n = arr.length;\n\n for (let i = 1; i < n; i++) {\n const key: number = arr[i];\n let j: number = i - 1;\n\n // Shift elements that are greater than key to the right\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n\n // Place key in its correct position\n arr[j + 1] = key;\n }\n}\n```\n\n\nThe outer loop picks each unsorted element starting from index 1. The inner while loop shifts larger elements to the right. After the loop, the key is placed into the correct position.\n\n\n\n\n\n---\n\n# Example Walkthrough\n\nTrace the algorithm on the array `[7, 3, 5, 1, 9, 2]`, stepping through each iteration.\n\n### Initial State\n\n\n```shell\nArray: [7, 3, 5, 1, 9, 2]\n ^\n Sorted region (just index 0)\n```\n\n\n### Step 1: i = 1, key = 3\n\nCompare `3` with elements in the sorted region (just `7`).\n\n- `7 > 3`, so shift `7` one position to the right.\n- No more elements to compare. Place `3` at index 0.\n\n\n```shell\nBefore: [7, 3, 5, 1, 9, 2]\n ^ ^\n | key = 3\n shift right\n\nAfter: [3, 7, 5, 1, 9, 2]\n ----\n sorted\n```\n\n\n### Step 2: i = 2, key = 5\n\nCompare `5` with elements in the sorted region `[3, 7]`, moving right to left.\n\n- `7 > 5`, so shift `7` to the right.\n- `3 < 5`, so stop. Place `5` at index 1.\n\n\n```shell\nBefore: [3, 7, 5, 1, 9, 2]\n ^ ^\n | key = 5\n shift right\n\nAfter: [3, 5, 7, 1, 9, 2]\n -------\n sorted\n```\n\n\n### Step 3: i = 3, key = 1\n\nCompare `1` with elements in the sorted region `[3, 5, 7]`, moving right to left.\n\n- `7 > 1`, shift right.\n- `5 > 1`, shift right.\n- `3 > 1`, shift right.\n- No more elements. Place `1` at index 0.\n\n\n```shell\nBefore: [3, 5, 7, 1, 9, 2]\n ^ ^ ^ ^\n | | | key = 1\n shift all right\n\nAfter: [1, 3, 5, 7, 9, 2]\n ----------\n sorted\n```\n\n\nThis is the worst case for a single insertion. The element `1` had to travel all the way to the front, requiring every sorted element to shift.\n\n### Step 4: i = 4, key = 9\n\nCompare `9` with the last element in the sorted region.\n\n- `7 < 9`, so stop immediately. Place `9` at index 4 (it stays in place).\n\n\n```shell\nBefore: [1, 3, 5, 7, 9, 2]\n ^\n key = 9 (already in place)\n\nAfter: [1, 3, 5, 7, 9, 2]\n -------------\n sorted\n```\n\n\nThis is the best case for a single insertion. When an element is already larger than everything in the sorted region, no shifting is needed. The same scenario across every insertion is what makes Insertion Sort fast on nearly sorted data.\n\n### Step 5: i = 5, key = 2\n\nCompare `2` with elements in the sorted region `[1, 3, 5, 7, 9]`, moving right to left.\n\n- `9 > 2`, shift right.\n- `7 > 2`, shift right.\n- `5 > 2`, shift right.\n- `3 > 2`, shift right.\n- `1 < 2`, stop. Place `2` at index 1.\n\n\n```shell\nBefore: [1, 3, 5, 7, 9, 2]\n ^ ^ ^ ^ ^\n | | | | key = 2\n shift all right\n\nAfter: [1, 2, 3, 5, 7, 9]\n ----------------\n fully sorted\n```\n\n\n### Final Result\n\n\n```shell\n[1, 2, 3, 5, 7, 9]\n```\n\n\nThe algorithm made 5 passes (for elements at indices 1 through 5), performing a total of 12 comparisons and 9 shifts. The number of shifts ranged from 0 (for `9`) to 4 (for `2`), which reflects the adaptive behavior of Insertion Sort: an element already in position costs nothing, while one far from its place costs several shifts.\n\n\n```mermaid\nflowchart TD\n S0[\"[7, 3, 5, 1, 9, 2]
Initial array\"]\n S1[\"[3, 7, 5, 1, 9, 2]
Insert 3: 1 shift\"]\n S2[\"[3, 5, 7, 1, 9, 2]
Insert 5: 1 shift\"]\n S3[\"[1, 3, 5, 7, 9, 2]
Insert 1: 3 shifts\"]\n S4[\"[1, 3, 5, 7, 9, 2]
Insert 9: 0 shifts\"]\n S5[\"[1, 2, 3, 5, 7, 9]
Insert 2: 4 shifts\"]\n\n S0 --> S1 --> S2 --> S3 --> S4 --> S5\n\n style S0 fill:#ff8787,stroke:#000,color:#000\n style S1 fill:#ffa94d,stroke:#000,color:#000\n style S2 fill:#ffa94d,stroke:#000,color:#000\n style S3 fill:#ffa94d,stroke:#000,color:#000\n style S4 fill:#ffa94d,stroke:#000,color:#000\n style S5 fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# Complexity Analysis\n\n\n| Case | Time Complexity | Explanation |\n|------|----------------|-------------|\n| Best | O(n) | Array is already sorted. The inner loop never executes. Each element is compared once and stays in place. |\n| Average | O(n^2) | On average, each element needs to be compared with half of the sorted region. |\n| Worst | O(n^2) | Array is sorted in reverse order. Every element must travel all the way to the front, causing maximum shifts. |\n| Space | O(1) | Only a constant amount of extra memory is used (the `key` variable and loop counters). |\n\n\n**Adaptive:** Yes. The running time depends on how \"sorted\" the input already is. If the input has very few inversions (pairs of elements that are out of order), Insertion Sort runs close to O(n). This adaptive property is what makes it valuable for nearly sorted data.\n\n### Stability\n\nInsertion Sort is stable. The inner while loop's condition uses strict greater-than (`arr[j] > key`), so it never shifts an element that equals the key. A new equal element comes to rest just after the existing ones, which preserves their original relative order.\n\nThis stability is the reason hybrid algorithms like TimSort and Introsort fall back to Insertion Sort for small runs: they retain the overall sort's stability guarantee while exploiting Insertion Sort's low overhead on small inputs.\n\nThe following table shows comparisons for 10,000 elements in different scenarios:\n\n\n| Scenario | Approximate Comparisons |\n|----------|------------------------|\n| Already sorted | 9,999 |\n| Nearly sorted (10 inversions) | ~10,009 |\n| Random order | ~25,000,000 |\n| Reverse sorted | ~50,000,000 |\n\n\nThe gap between best and worst case spans roughly four orders of magnitude. For nearly sorted data, Insertion Sort is competitive with O(n log n) algorithms. For random data, it is not.\n\n---\n\n# When to Use Insertion Sort\n\n### Good Use Cases\n\n**Nearly sorted data.** If the input is almost sorted with only a few elements out of place, Insertion Sort's adaptive nature makes it highly efficient. Each out-of-place element only needs a small number of shifts.\n\n**Small arrays.** For arrays with fewer than 10-20 elements, the overhead of more complex algorithms like Merge Sort or Quick Sort (function call overhead, partitioning logic) makes them slower than Insertion Sort. The low constant factors of Insertion Sort give it an edge on small inputs.\n\n**Online sorting (sorting as data arrives).** When elements arrive one at a time and the collection must stay sorted, Insertion Sort handles each arrival directly. Each new element is inserted into its correct position as it comes in.\n\n**As a subroutine in hybrid algorithms.** Hybrid algorithms are the most common practical use case. Production sorting implementations use Insertion Sort as a building block:\n\n- **TimSort** (used by Python and Java) switches to Insertion Sort for small runs (typically fewer than 64 elements).\n- **Introsort** (used by C++ STL) falls back to Insertion Sort when the partition size drops below a threshold (typically 16 elements).\n- **Shell Sort** uses Insertion Sort as its core operation, but with varying gap sizes to move elements faster.\n\n### When to Avoid\n\n**Large random datasets.** With O(n^2) average-case complexity, Insertion Sort cannot compete with O(n log n) algorithms for large inputs. Sorting 1 million random elements with Insertion Sort takes roughly 250 billion comparisons on average (500 billion in the worst case), while Merge Sort needs about 20 million.\n\n**Performance-critical paths with unpredictable data.** If the input is not guaranteed to be small or nearly sorted, use a general-purpose O(n log n) algorithm instead.\n\nThe following table summarizes the trade-offs:\n\n\n| Factor | Insertion Sort | Merge Sort | Quick Sort |\n|--------|---------------|------------|------------|\n| Best case | O(n) | O(n log n) | O(n log n) |\n| Worst case | O(n^2) | O(n log n) | O(n^2) |\n| Space | O(1) | O(n) | O(log n) |\n| Stable | Yes | Yes | No |\n| Adaptive | Yes | No | No |\n| Small arrays | Excellent | Overhead | Overhead |\n\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium