New: 77 pattern programs with tested code in C, C++, Java and Python Explore patterns

Insertion Sort in C: Program, Pseudocode and Examples

Read summary with AI tools
Table of contents
  1. How insertion sort works
  2. Real-life example
  3. Pseudocode for insertion sort
  4. Step-by-step example
  5. Program 1: Insertion sort in C using a for loop
  6. Program 2: Insertion sort in C using a while loop
  7. Program 3: Insertion sort in C using a function
  8. Time and space complexity
  9. Advantages of insertion sort
  10. Disadvantages of insertion sort
  11. Frequently asked questions

Insertion sort sorts an array the way most people sort playing cards in their hand: take the next card and slide it left until it sits in the right place among the cards already sorted. It is simple, works in place, and is very fast on small or nearly sorted arrays.

In this post you will learn how insertion sort works step by step, its pseudocode and time complexity, and three complete C programs: with a for loop and user input, with while loops, and with a function that prints every pass.

How insertion sort works

  1. The first element on its own is already “sorted”.
  2. Take the next element (the key) and compare it with the elements to its left.
  3. Shift every element that is larger than the key one place to the right.
  4. Drop the key into the gap that is left.
  5. Repeat for every element until the end of the array.

Real-life example

Imagine you are dealt cards one at a time. You keep the cards in your hand sorted: each new card is compared with the cards from right to left and inserted where it belongs. Insertion sort does exactly this with the elements of an array.

Pseudocode for insertion sort

for i from 1 to n - 1
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key

Step-by-step example

Sorting the array 8 3 5 1 9 2. In every pass the key is inserted into the sorted part on the left (this is the real output of program 3 below):

PassKey insertedArray after the pass
Original–8 3 5 1 9 2
Pass 133 8 5 1 9 2
Pass 253 5 8 1 9 2
Pass 311 3 5 8 9 2
Pass 491 3 5 8 9 2
Pass 521 2 3 5 8 9
Insertion sort passes on the array 8 3 5 1 9 2, showing where each key is inserted
Each pass takes the next key and inserts it into the sorted part on the left.

Program 1: Insertion sort in C using a for loop

This program reads the numbers from the user and sorts them in ascending order.

#include <stdio.h>

int main(void) {
    int n;

    printf("How many numbers do you want to sort? ");
    scanf("%d", &n);

    int a[n];
    printf("Enter %d numbers: ", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    /* insertion sort */
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j;
        /* shift every larger element one place to the right */
        for (j = i - 1; j >= 0 && a[j] > key; j--)
            a[j + 1] = a[j];
        a[j + 1] = key;
    }

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Sample run:

How many numbers do you want to sort? 6
Enter 6 numbers: 8 3 5 1 9 2
Sorted array: 1 2 3 5 8 9 

Program 2: Insertion sort in C using a while loop

The same algorithm written with while loops and a fixed array, so you can run it without typing any input.

#include <stdio.h>

int main(void) {
    int a[] = {8, 3, 5, 1, 9, 2};
    int n = sizeof(a) / sizeof(a[0]);

    int i = 1;
    while (i < n) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
        i++;
    }

    printf("Sorted array: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Output:

Sorted array: 1 2 3 5 8 9 

Program 3: Insertion sort in C using a function

Here the sorting is moved into its own function, insertion_sort(), which also prints the array after every pass so you can watch the algorithm work.

#include <stdio.h>

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

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

        printf("Pass %d: ", i);
        print_array(a, n);
    }
}

int main(void) {
    int a[] = {8, 3, 5, 1, 9, 2};
    int n = sizeof(a) / sizeof(a[0]);

    printf("Original: ");
    print_array(a, n);
    insertion_sort(a, n);
    printf("Sorted:   ");
    print_array(a, n);
    return 0;
}

Output:

Original: 8 3 5 1 9 2 
Pass 1: 3 8 5 1 9 2 
Pass 2: 3 5 8 1 9 2 
Pass 3: 1 3 5 8 9 2 
Pass 4: 1 3 5 8 9 2 
Pass 5: 1 2 3 5 8 9 
Sorted:   1 2 3 5 8 9 

Time and space complexity

CaseComplexity
Best case (already sorted)O(n)
Average caseO(n²)
Worst case (reverse sorted)O(n²)
Extra spaceO(1), sorts in place
Stable?Yes, equal elements keep their order

Advantages of insertion sort

  • Very simple to write and understand.
  • Fast for small arrays and for arrays that are already nearly sorted.
  • Sorts in place with O(1) extra memory.
  • Stable, and can sort data as it arrives (online).

Disadvantages of insertion sort

  • O(n²) comparisons and shifts in the average and worst case.
  • Much slower than merge sort, heap sort or quick sort on large arrays.

Frequently asked questions

Is insertion sort stable?

Yes. An element is only moved past elements that are strictly greater than it, so equal elements keep their original order.

When should I use insertion sort?

For small arrays (a few dozen elements) or data that is almost sorted. Many libraries switch to insertion sort for small sub-arrays inside faster algorithms.

How do I sort in descending order?

Change the comparison a[j] > key to a[j] < key.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.