Insertion Sort in C, C++ & Java | Examples & Time Complexity

Introduction

Insertion Sort is a simple yet effective comparison-based sorting algorithm widely used for small datasets and nearly sorted arrays. It works similarly to sorting playing cards in your hand—by placing each new card (element) in its correct position.

In this article, we will cover:

• How Insertion Sort works with a step-by-step explanation
• Insertion Sort algorithm with pseudocode
• Implementation in C, C++, and Java
• Time complexity analysis

Before diving in, you may want to review Bubble Sort and Selection Sort, as they follow similar iterative approaches.

What is Insertion Sort?

Insertion Sort builds the final sorted array one element at a time by:

1. Picking an element from the unsorted portion of the array.
2. Placing it in its correct position within the sorted portion.
3. Shifting the larger elements to the right to make space.

This process continues until all elements are correctly placed.

How Insertion Sort Works: Step-by-Step Example

Let’s take an example array:
Input Array: [7, 1, 23, 4, 19]

Step-by-Step Execution:

At the end of these iterations, the array is sorted: [1, 4, 7, 19, 23].

Insertion Sort Algorithm (Pseudocode)

for i = 1 to n-1
    key = arr[i]
    j = i - 1

    while j >= 0 and arr[j] > key
        arr[j + 1] = arr[j]  // Shift elements
        j = j - 1

    arr[j + 1] = key  // Insert key at correct position

Insertion Sort Implementation in C, C++, and Java

C Implementation of Insertion Sort

#include <stdio.h>

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;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {7, 1, 23, 4, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

C++ Implementation of Insertion Sort

#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;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {7, 1, 23, 4, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Java Implementation of Insertion Sort

class InsertionSort {
    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; 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;
        }
    }

    static void printArray(int[] arr) {
        for (int num : arr)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 23, 4, 19};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        printArray(arr);
    }
}

Time Complexity of Insertion Sort

Why?

• In the worst case (when the array is sorted in reverse order), each element is compared with all previous elements, making the complexity O(n²).
• In the best case (when the array is already sorted), only one comparison per element is needed, making it O(n).

Space Complexity: O(1) (In-place sorting algorithm)

Insertion Sort vs Other Sorting Algorithms

Conclusion

Insertion Sort is a simple and efficient sorting algorithm for small datasets or nearly sorted arrays. While it is slower than Merge Sort and QuickSort, it has the advantage of being an in-place, stable sorting algorithm with O(1) space complexity.

When to Use Insertion Sort?

• When the dataset is small.
• When the array is partially sorted.
• When stable sorting is required.