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 a nested loop; 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; } to sort the array in place.

Examples

Input5 5 2 9 1 5

OutputSorted array: 1 2 5 5 9

Input3 3 3 3

OutputSorted array: 3 3 3

Input4 4 3 2 1

OutputSorted array: 1 2 3 4

How to Think About It

To sort using insertion sort, think of sorting cards in your hand. Start from the second element, compare it with elements before it, and shift larger elements one position right to make space. Insert the current element where it fits. Repeat this for all elements until the whole array is sorted.

Algorithm

1

Start from the second element of the array (index 1).

2

Store the current element as the key.

3

Compare the key with elements before it and shift those larger than the key one position to the right.

4

Insert the key into the correct position where no larger element is before it.

5

Repeat for all elements until the array is sorted.

Code

c

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

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    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 2 with 5; since 5 > 2, shift 5 right. Insert 2 at position 0. Array: [2, 5, 9, 1, 5]

2

i=2, key=9

Compare 9 with 5; 5 < 9, no shift. Insert 9 at position 2. Array: [2, 5, 9, 1, 5]

3

i=3, key=1

Shift 9, 5, 2 right as all > 1. Insert 1 at position 0. Array: [1, 2, 5, 9, 5]

4

i=4, key=5

Shift 9 right as 9 > 5. Insert 5 at position 3. Array: [1, 2, 5, 5, 9]

Iteration	Array State
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 element

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 larger than the key are moved one step right to make space for the key.

Step 3: Inserting the key

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

Alternative Approaches

Recursive insertion sort

c

#include <stdio.h>

void insertionSortRecursive(int arr[], int n) {
    if (n <= 1) return;
    insertionSortRecursive(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 n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    insertionSortRecursive(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Uses recursion instead of loops; easier to understand for some but uses more stack memory.

Using binary search to find insertion point

c

#include <stdio.h>

int binarySearch(int arr[], int item, int low, int high) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == item) return mid + 1;
        else if (arr[mid] < item) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

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

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    insertionSortBinary(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Uses binary search to find where to insert, reducing comparisons but still shifts elements.

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 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 slow for large data; binary search insertion reduces comparisons but not shifts; recursive version is less memory efficient.

Approach	Time	Space	Best For
Standard insertion sort	O(n^2)	O(1)	Small or nearly sorted arrays
Recursive insertion sort	O(n^2)	O(n) stack	Learning recursion, small arrays
Binary search insertion sort	O(n^2)	O(1)	Reducing comparisons, still small arrays