Insertion Sort in C – Program, Algorithm and Complexity

Insertion sort is one of the simplest sorting algorithms and works exactly the way you sort a hand of playing cards. You take one card at a time and insert it into its correct position among the cards already sorted in your hand. It sorts the array one element at a time, building the sorted portion from left to right.

While not efficient for large datasets, insertion sort has a key advantage: it performs in O(n) time on nearly-sorted arrays, making it the algorithm of choice for small arrays or as the final step in more complex sorts like Timsort.

How Insertion Sort Works — Step by Step

Start from the second element. For each element, compare it backward through the sorted portion and shift elements right until you find its correct position.

Example: Sorting [12, 11, 13, 5, 6]

Pass 1: key = 11
  [12, 11, 13, 5, 6]
   12 > 11 → shift right
  [11, 12, 13, 5, 6]

Pass 2: key = 13
  13 > 12 → already in place
  [11, 12, 13, 5, 6]

Pass 3: key = 5
  13 > 5 → shift, 12 > 5 → shift, 11 > 5 → shift
  [5, 11, 12, 13, 6]

Pass 4: key = 6
  13 > 6 → shift, 12 > 6 → shift, 11 > 6 → shift
  [5, 6, 11, 12, 13]  ← sorted

C Program for Insertion Sort

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    int n, i;
    int *arr;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    arr = (int *)malloc(n * sizeof(int));
    if (!arr) { fprintf(stderr, "malloc failed\n"); return 1; }

    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Before sorting: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    insertion_sort(arr, n);

    printf("\nAfter insertion sort: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    printf("\n");
    free(arr);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o insertsort insertsort.c
./insertsort

Code Explanation

Outer loop (i = 1 to n-1): Picks one unsorted element at a time as the key. The subarray arr[0..i-1] is always already sorted at the start of each pass.
key = arr[i]: Saves the current element before shifting begins — it would be overwritten otherwise.
Inner while loop: Scans left through the sorted portion. Every element larger than key shifts one position right, creating a gap for key to be placed.
arr[j + 1] = key: Places key in its correct sorted position — either at the start of the array or just after the last element that is smaller than it.

Sample Input and Output

Enter number of elements: 6
Enter 6 elements:
64 25 12 22 11 90

Before sorting: 64 25 12 22 11 90
After insertion sort: 11 12 22 25 64 90

Time and Space Complexity

Case	Time Complexity	When it occurs
Best case	O(n)	Array is already sorted — inner loop never executes
Average case	O(n²)	Elements in random order
Worst case	O(n²)	Array is sorted in reverse order — maximum shifts every pass

Space complexity: O(1) — insertion sort is an in-place algorithm. It uses only one extra variable (key) regardless of input size. This makes it memory-efficient compared to merge sort, which requires O(n) extra space.

The O(n) best-case performance is a genuine advantage. Algorithms like merge sort and heap sort always take O(n log n) even on sorted data — insertion sort skips all unnecessary work when the data is already in order.

Insertion Sort vs Other Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable	Adaptive
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	No
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	No

Adaptive means the algorithm runs faster on partially sorted input. Both insertion sort and bubble sort are adaptive — insertion sort is usually preferred because it does fewer swaps.

When to Use Insertion Sort

Small arrays (n < 20): The overhead of recursive algorithms like merge sort and quick sort outweighs their theoretical advantage for tiny inputs. Most standard library implementations switch to insertion sort below a threshold (e.g., Java uses 47 elements, Python’s Timsort uses 32–64).
Nearly sorted data: If only a few elements are out of place, insertion sort detects this and runs close to O(n).
Online sorting: When elements arrive one at a time and must be kept sorted after each insertion (e.g., a live leaderboard).
Linked lists: Insertion sort is efficient on linked lists because shifting is replaced by pointer updates.

Related Programs

As an Amazon Associate we earn from qualifying purchases.