C++ Program for Insertion Sort with Example and Explanation

An insertion sort in C++ can be done by looping through the array and inserting each element into its correct position using for and while loops; for example, use for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; }.

Examples

Inputarr = {5, 2, 9, 1, 5}

OutputSorted array: 1 2 5 5 9

Inputarr = {1, 2, 3, 4, 5}

OutputSorted array: 1 2 3 4 5

Inputarr = {10}

OutputSorted array: 10

How to Think About It

To sort an array using insertion sort, think of sorting cards in your hand. Start from the second element, compare it with elements before it, and move it left until it is in the right place. Repeat this for each element until the whole array is sorted.

Algorithm

1

Start from the second element of the array.

2

Store the current element as the key.

3

Compare the key with elements before it and shift those elements one position to the right if they are greater than the key.

4

Insert the key into the correct position.

5

Repeat for all elements until the array is sorted.

Code

cpp

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {5, 2, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Output

Sorted array: 1 2 5 5 9 

Dry Run

Let's trace the array {5, 2, 9, 1, 5} through the insertion sort code.

1

Start with i=1, key=2

Compare key=2 with arr[0]=5, since 5 > 2, shift 5 right. Array becomes {5, 5, 9, 1, 5}. Insert key=2 at arr[0]. Array now {2, 5, 9, 1, 5}.

2

i=2, key=9

Compare key=9 with arr[1]=5, 5 < 9, no shift. Insert key=9 at arr[2]. Array unchanged {2, 5, 9, 1, 5}.

3

i=3, key=1

Compare key=1 with arr[2]=9, shift 9 right. Compare with arr[1]=5, shift 5 right. Compare with arr[0]=2, shift 2 right. Insert key=1 at arr[0]. Array now {1, 2, 5, 9, 5}.

4

i=4, key=5

Compare key=5 with arr[3]=9, shift 9 right. Compare with arr[2]=5, 5 not greater than 5, stop. Insert key=5 at arr[3]. Array now {1, 2, 5, 5, 9}.

Iteration	Array State
Start	5 2 9 1 5
i=1	2 5 9 1 5
i=2	2 5 9 1 5
i=3	1 2 5 9 5
i=4	1 2 5 5 9

Why This Works

Step 1: Choosing the key

We pick the element at index i as the key to insert it into the sorted part on the left.

Step 2: Shifting elements

Elements greater than the key are moved one position right to make space for the key.

Step 3: Inserting the key

The key is placed in the correct position where all elements to the left are smaller or equal.

Alternative Approaches

Using std::vector and iterators

cpp

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& vec) {
    for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
        int key = *it;
        auto jt = it - 1;
        while (jt >= vec.begin() && *jt > key) {
            *(jt + 1) = *jt;
            if (jt == vec.begin()) {
                --jt;
                break;
            }
            --jt;
        }
        *(jt + 1) = key;
    }
}

int main() {
    vector<int> vec = {5, 2, 9, 1, 5};
    insertionSort(vec);
    cout << "Sorted array: ";
    for (int v : vec) cout << v << " ";
    cout << endl;
    return 0;
}

This uses C++ vectors and iterators for safer and more flexible code but is slightly more complex.

Using recursion

cpp

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    if (n <= 1) return;
    insertionSort(arr, n - 1);
    int last = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

int main() {
    int arr[] = {5, 2, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

This recursive approach is elegant but less efficient and harder to understand for beginners.

Complexity: O(n^2) time, O(1) space

Time Complexity

Insertion sort uses nested loops: the outer loop runs n times, and the inner loop can run up to n times in the worst case, making it O(n^2).

Space Complexity

It sorts the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

Insertion sort is simple but slower on large arrays compared to quicksort or mergesort, which have O(n log n) average time.

Approach	Time	Space	Best For
Insertion Sort	O(n^2)	O(1)	Small or nearly sorted arrays
Vector with Iterators	O(n^2)	O(1)	Safer C++ code with dynamic arrays
Recursive Insertion Sort	O(n^2)	O(n) due to recursion stack	Educational or small inputs