Insertion Sort Implementation

Problem Statement

Sort an array using insertion sort: take each element and insert it into its correct position within the already-sorted prefix to its left.

Example

Input:  [5, 2, 4, 6, 1, 3]
Insert 2 -> [2,5,4,6,1,3] -> ...
Output: [1, 2, 3, 4, 5, 6]

Approach

For each index i, hold key = arr[i] and shift every larger element in the sorted prefix one step right, then drop the key into the gap. It is very fast on small or nearly sorted arrays and is the basis of the small-array cutoff inside Timsort and introsort.

Complexity

• Time: O(n^2) worst/average, O(n) best (nearly sorted)
• Space: O(1)

Solution Code

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

Java

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

C++

void insertionSort(vector<int>& arr) {
    for (int i = 1; i < (int)arr.size(); i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Key Takeaways

• Insertion sort is stable, in-place, and excellent on small or nearly sorted inputs.
• Real libraries switch to it for small subarrays inside faster sorts.
• Reference: CLRS, Ch. 2; Wikipedia, "Insertion sort".