{"title":"Insertion Sort","description":"","content":"Insertion Sort builds a sorted array one element at a time. It takes each element and inserts it into its correct position within the already sorted portion, much like sorting playing cards in your hand.\n\nAt every step, the algorithm shifts larger elements to the right to make space for the current element. This makes it efficient for small datasets and nearly sorted arrays, where only a few shifts are needed.\n\nWhile it is not suitable for large inputs, Insertion Sort is an important algorithm to understand because of its simplicity, stability, and practical performance in specific scenarios.\n\nIn this chapter, you will learn how Insertion Sort works step by step, how to implement it, and when it can outperform 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\nWhy is this considered the most intuitive sorting algorithm? Because it does not require any clever tricks or complex data structures. You look at each element, compare it to what you have already sorted, and put it in the right place. That is it.\n\nThis simplicity makes it an excellent starting point for understanding sorting algorithms. But do not let the simplicity fool you. Insertion Sort has real practical value, especially in scenarios where data is nearly sorted or arriving in a stream.\n\n---\n\n# How It Works\n\nHere is the step-by-step process:\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 key insight here is **shifting, not swapping**. Many beginners implement Insertion Sort using adjacent swaps, but the standard approach shifts elements to the right in a single pass and then places the key in its final position. This is more efficient because 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\nNotice the inner while loop. It keeps shifting elements to the right as long as they are greater than the key. The moment it finds an element that is smaller than or equal to the key, it stops. The key drops into the gap right after that element. This is what makes Insertion Sort stable: equal elements maintain their original relative order because we only shift elements that are strictly greater than the key.\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```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```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# Example Walkthrough\n\nLet us trace through the algorithm with the array `[7, 3, 5, 1, 9, 2]`. We will go step by step to see exactly what happens during 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\nWe compare `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\nWe compare `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\nWe compare `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\nWe compare `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. This is why Insertion Sort is fast on nearly sorted data.\n\n### Step 5: i = 5, key = 2\n\nWe compare `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 11 comparisons and 11 shifts. Notice how the number of shifts varied dramatically per step, from 0 (for `9`) to 4 (for `2`). This is what gives Insertion Sort its adaptive behavior.\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**Stability:** Yes. Insertion Sort is stable because it only shifts elements that are strictly greater than the key. Equal elements are never reordered relative to each other.\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 so valuable for nearly sorted data.\n\nTo put the numbers in perspective, consider sorting 10,000 elements:\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 difference between the best case and worst case is enormous. 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 extremely 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) actually makes them slower than Insertion Sort. The simplicity of Insertion Sort shines on small inputs.\n\n**Online sorting (sorting as data arrives).** When you receive elements one at a time and need to maintain a sorted collection, Insertion Sort is a natural fit. Each new element is simply inserted into the correct position.\n\n**As a subroutine in hybrid algorithms.** This is perhaps the most important practical use case. Real-world 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 simply cannot compete with O(n log n) algorithms for large inputs. Sorting 1 million random elements with Insertion Sort would take roughly 500 billion comparisons, while Merge Sort would need about 20 million.\n\n**Performance-critical paths with unpredictable data.** If you cannot guarantee the input is 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","pageType":"dsa"}

Insertion Sort

Ashish Pratap Singh

Get Premium