Insertion Sort in C++

Insertion Sort Algorithm in C++ (Complete Implementation).

BeginnerSorting & Searching ProgramsExample 2 of 13

insertion-sort.cpp

1#include <iostream>
2using namespace std;
3
4void insertionSort(int arr[], int n) {
5    for (int i = 1; i < n; i++) {
6        int key = arr[i];
7        int j = i - 1;
8        
9        // Move elements greater than key one position ahead
10        while (j >= 0 && arr[j] > key) {
11            arr[j + 1] = arr[j];
12            j--;
13        }
14        arr[j + 1] = key;
15    }
16}
17
18void printArray(int arr[], int n) {
19    for (int i = 0; i < n; i++) {
20        cout << arr[i] << " ";
21    }
22    cout << endl;
23}
24
25int main() {
26    int arr[] = {64, 34, 25, 12, 22, 11, 90};
27    int n = sizeof(arr) / sizeof(arr[0]);
28    
29    cout << "Original array: ";
30    printArray(arr, n);
31    
32    insertionSort(arr, n);
33    
34    cout << "Sorted array: ";
35    printArray(arr, n);
36    
37    return 0;
38}

Output

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

What's going on

The program sorts an array of integers using the Insertion Sort algorithm. For example:

Input array: [64, 34, 25, 12, 22, 11, 90]

Output array: [11, 12, 22, 25, 34, 64, 90]

Insertion Sort builds the sorted array incrementally by inserting each element into its correct position in the already sorted portion.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Insertion Sort

Algorithm Concept

Maintains a sorted subarray at the beginning

Takes next element and inserts it in correct position

Shifts larger elements to make room

Similar to sorting cards in hand

Visual Example

Initial: [64, 34, 25, 12, 22, 11, 90]

Step 1: [34, 64, 25, 12, 22, 11, 90] (insert 34 before 64)

Step 2: [25, 34, 64, 12, 22, 11, 90] (insert 25 at beginning)

Step 3: [12, 25, 34, 64, 22, 11, 90] (insert 12 at beginning)

Step 4: [12, 22, 25, 34, 64, 11, 90] (insert 22 after 12)

Step 5: [11, 12, 22, 25, 34, 64, 90] (insert 11 at beginning)

Step 6: [11, 12, 22, 25, 34, 64, 90] (90 already in place)

Function: insertionSort()

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;

}

How it works

Outer loop (i): iterates from 1 to n-1 (each element to insert)

key: current element to be inserted

Inner while loop: shifts larger elements right

Inserts key in correct position

Step-by-Step Algorithm

For each element arr[i] (starting from i=1)

Step 1: Store Current Element

key = arr[i] (element to be inserted)

Step 2: Find Insertion Position

Compare key with elements in sorted portion (arr[0] to arr[i-1])

Shift elements greater than key one position right

Continue until correct position found

Step 3: Insert Element

Place key in correct position

Sorted portion grows by one element

Example

(inserting 22 when sorted portion is [12, 25, 34, 64]):

key = 22

Compare: 64 > 22 → shift 64 right

Compare: 34 > 22 → shift 34 right

Compare: 25 > 22 → shift 25 right

Compare: 12 < 22 → stop

Insert 22 after 12

Understanding the Inner While Loop

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j--;

}

How it works

j starts at i - 1 (last element of sorted portion)

Condition: j >= 0 (within bounds) AND arr[j] > key (need to shift)

arr[j + 1] = arr[j] shifts element right

j-- moves to previous element

Stops when correct position found

Why j >= 0?

Prevents accessing arr[-1]

Ensures we stay within array bounds

Stops at beginning of sorted portion

Time and Space Complexity

Time Complexity

Worst case: O(n²) - array in reverse order

Best case: O(n) - array already sorted

Average case: O(n²)

Space Complexity

: O(1)

Only uses constant extra space

Sorts in-place (modifies original array)

Stability

: Stable

Equal elements maintain their relative order

Important for sorting objects with multiple fields

When to Use Insertion Sort

Best For

Small datasets (< 50 elements)

Nearly sorted arrays

Online algorithms (sorting as data arrives)

Simple implementation needed

Not Recommended For

Large datasets (use Quick Sort, Merge Sort)

Random data (better algorithms available)

Performance-critical applications

Important Considerations

Starting Index

Outer loop starts at i = 1 (not 0)

First element (arr[0]) is already "sorted"

Each iteration adds one element to sorted portion

Shifting Elements

Elements are shifted right, not swapped

More efficient than swapping

Preserves relative order

Key Variable

Store arr[i] in key before shifting

Prevents losing the value during shifts

Insert key after finding position

return 0;

This ends the program successfully.

PreviousBubble Sort NextSelection Sort