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
- The first element on its own is already “sorted”.
- Take the next element (the key) and compare it with the elements to its left.
- Shift every element that is larger than the key one place to the right.
- Drop the key into the gap that is left.
- 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] = keyStep-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):
| Pass | Key inserted | Array after the pass |
|---|---|---|
| Original | – | 8 3 5 1 9 2 |
| Pass 1 | 3 | 3 8 5 1 9 2 |
| Pass 2 | 5 | 3 5 8 1 9 2 |
| Pass 3 | 1 | 1 3 5 8 9 2 |
| Pass 4 | 9 | 1 3 5 8 9 2 |
| Pass 5 | 2 | 1 2 3 5 8 9 |

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
| Case | Complexity |
|---|---|
| Best case (already sorted) | O(n) |
| Average case | O(n²) |
| Worst case (reverse sorted) | O(n²) |
| Extra space | O(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.





