Insertion Sort

Jul 30, 2026tmdeveloper007

EditReport

Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by taking each element and inserting it into its correct position within the already-sorted portion of the array.

How It Works

The algorithm maintains a sorted portion at the beginning of the array. For each unsorted element, it finds the correct position in the sorted portion and shifts elements to make room.

Step-by-Step Walkthrough

Given array: [5, 3, 4, 1, 2]

Pass 1: Take 3, insert before 5 -> [3, 5, 4, 1, 2] Pass 2: Take 4, insert between 3 and 5 -> [3, 4, 5, 1, 2] Pass 3: Take 1, insert at beginning -> [1, 3, 4, 5, 2] Pass 4: Take 2, insert between 1 and 3 -> [1, 2, 3, 4, 5]

Implementation

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example usage
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr)  # Output: [5, 6, 11, 12, 13]

JavaScript

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Complexity Analysis

Case	Time Complexity	Space Complexity
Best Case	$O(n)$	$O(1)$
Average Case	$O(n^2)$	$O(1)$
Worst Case	$O(n^2)$	$O(1)$

Best Case

Occurs when the array is already sorted. Each element is compared only once with the previous element, yielding $O(n)$.

Worst Case

Occurs when the array is in reverse sorted order. Each element must be compared with all previously sorted elements.

When to Use Insertion Sort

• Small datasets: Faster than $O(n \log n)$ algorithms for small $n$ (typically $n < 50$)
• Nearly sorted data: Excellent performance when data is almost sorted
• Online sorting: Can sort data as it arrives, without needing all elements upfront
• Adaptive: Naturally adapts to partially sorted data
• Stable sort: Does not change the relative order of equal elements

Optimizations

Binary Insertion Sort

Use binary search to find the insertion position, reducing comparisons from $O(n^2)$ to $O(n \log n)$, but shifts remain $O(n^2)$.

import bisect

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = bisect.bisect_left(arr, key, 0, i)
        arr.pop(i)
        arr.insert(j, key)
    return arr

Comparison with Other O(n^2) Algorithms

Feature	Insertion Sort	Selection Sort	Bubble Sort
Best case time	$O(n)$	$O(n^2)$	$O(n)$
Adaptive	Yes	No	Yes
Stable	Yes	No	Yes
Swaps needed	$O(n)$ avg	$O(n)$	$O(n^2)$

Pseudocode

for i = 1 to n-1:
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key