C Insertion Sort
Insertion sort is a simple, intuitive sorting algorithm that builds a sorted array one element at a time, the same way most people sort a hand of playing cards. It repeatedly takes the next unsorted element and inserts it into its correct position among the elements that are already sorted. It isn’t the fastest algorithm for large datasets, but it sorts in place, uses almost no extra memory, and is remarkably efficient on small or nearly-sorted arrays — which is exactly why production sorting routines (including hybrid quicksorts and Timsort) fall back to insertion sort once a partition gets small.
Overview / How It Works
Insertion sort splits the array into two conceptual regions: a sorted region at the front and an unsorted region at the back. Initially the sorted region contains just the first element (a single element is trivially sorted), and the unsorted region is everything else. The algorithm then repeats the following: take the first element of the unsorted region, call it the key, and slide it leftward through the sorted region until it lands in its correct spot. Every element in the sorted region that is larger than key gets shifted one slot to the right to make room.
In C, this all happens on a single array in memory — there is no second array allocated. The key variable is a local copy of the value being inserted (saved before anything is overwritten), and the shifting is done with plain assignments, arr[j + 1] = arr[j], not full three-way swaps. That matters: a swap-based algorithm like bubble sort does three memory writes per exchange, while insertion sort’s shift is a single write per step, followed by one final write to place the key. This makes insertion sort do noticeably less memory traffic than swap-based sorts for the same number of comparisons.
Complexity
| Case | Time | Why |
|---|---|---|
| Best (already sorted) | O(n) | Each key only needs one comparison against its left neighbor before stopping. |
| Average | O(n2 | About half of the sorted region is shifted for each key, on average. |
| Worst (reverse sorted) | O(n2 | Every key must shift past the entire sorted region. |
Space complexity is O(1) extra space (in-place), and, written correctly, insertion sort is stable: elements that compare equal keep their original relative order.
Syntax
The general shape of an insertion sort function on an array of int looks like this:
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // element to insert
int j = i - 1; // last index of the sorted region
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift larger element right
j--;
}
arr[j + 1] = key; // insert key into its correct slot
}
}| Part | Meaning |
|---|---|
i |
Index of the next unsorted element being inserted; starts at 1 because a single element (index 0) is already "sorted". |
key |
A local copy of arr[i], saved before the slot gets overwritten by shifting. |
j |
Walks backward through the sorted region, from i - 1 down to -1. |
while condition |
Keeps shifting while there is still sorted-region data (j >= 0) that is greater than key. |
arr[j + 1] = key; |
Drops the key into the gap left by the last shift — its final sorted position. |
Examples
Example 1: Basic ascending 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(void) {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before: ");
printArray(arr, n);
insertionSort(arr, n);
printf("After: ");
printArray(arr, n);
return 0;
}Output:
Before: 12 11 13 5 6
After: 5 6 11 12 13 The array starts unsorted; after insertionSort runs, it is sorted in place — the same arr array, no new memory allocated.
Example 2: Watching each pass
To really see how the sorted region grows, this version prints the array after every outer-loop iteration:
#include <stdio.h>
void insertionSortVerbose(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;
printf("Pass %d: ", i);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
int main(void) {
int arr[] = {8, 4, 23, 42, 16, 15};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSortVerbose(arr, n);
return 0;
}Output:
Pass 1: 4 8 23 42 16 15
Pass 2: 4 8 23 42 16 15
Pass 3: 4 8 23 42 16 15
Pass 4: 4 8 16 23 42 15
Pass 5: 4 8 15 16 23 42 Notice passes 2 and 3 change nothing — 23 and 42 are already larger than everything to their left, so the while loop exits immediately (best-case behavior, one comparison, no shifts). Passes 4 and 5 show 16 and then 15 shifting multiple elements to the right as they migrate into position.
Example 3: Sorting an array of structs
Real programs rarely sort bare integers. Here, an array of Student records is sorted by score, descending:
#include <stdio.h>
typedef struct {
char name[20];
int score;
} Student;
void sortByScoreDesc(Student arr[], int n) {
for (int i = 1; i < n; i++) {
Student key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].score < key.score) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main(void) {
Student students[] = {
{"Alice", 72},
{"Bob", 95},
{"Charlie", 61},
{"Dana", 88}
};
int n = sizeof(students) / sizeof(students[0]);
sortByScoreDesc(students, n);
for (int i = 0; i < n; i++) {
printf("%-10s %d\n", students[i].name, students[i].score);
}
return 0;
}Output:
Bob 95
Dana 88
Alice 72
Charlie 61The whole Student struct is copied into key and shifted with arr[j + 1] = arr[j], exactly like the int version — insertion sort works on any type as long as you can compare and copy it. Only the comparison (< on score for descending order) and the element type change.
Under the Hood: Step by Step
Walking through one iteration for arr = {5, 3, 8} at i = 1:
key = arr[1]saves3before it can be overwritten.j = 0; checkarr[0] > key→5 > 3is true, so shift:arr[1] = arr[0], array is now{5, 5, 8}, andjbecomes-1.- The loop condition
j >= 0is now false, so it stops. arr[j + 1] = keywritesarr[0] = 3, giving{3, 5, 8}.
Each outer iteration does at most i comparisons and i shifts, so summing over all n elements gives roughly n2/2 operations in the worst case — the source of the O(n2) bound. On nearly-sorted data, the inner while loop usually exits on its first check, which is why insertion sort approaches O(n) on data that is already close to sorted — a property most other O(n2) sorts don’t share.
Common Mistakes
Mistake 1: Using an unsigned index for j
It’s tempting to make the inner index the same type as n from sizeof (which is size_t, an unsigned type). This is a classic C bug:
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
size_t j = i - 1; /* BUG: unsigned index type */
while (j >= 0 && arr[j] > key) { /* j >= 0 is ALWAYS true for size_t */
arr[j + 1] = arr[j];
j--; /* underflows to a huge number when j hits 0 */
}
arr[j + 1] = key;
}
}Because size_t is unsigned, j >= 0 is always true — it can never be false. When j reaches 0 and gets decremented, it doesn’t become -1; it wraps around to a huge positive number (SIZE_MAX), and arr[j] reads far out of bounds. This is undefined behavior and typically crashes. The fix is to use a plain signed int for j so it can legitimately go negative and stop the loop:
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1; /* FIX: use a signed type so j can go to -1 */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main(void) {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Output:
1 2 5 5 6 9 Mistake 2: Using >= instead of >, breaking stability
Swapping the comparison to arr[j] >= key looks harmless — the sort still produces correct values — but it silently shifts equal elements past the key, reversing their relative order. This program tags each value with an origin letter to expose the bug:
#include <stdio.h>
typedef struct {
int value;
char id;
} Item;
void insertionSortUnstable(Item arr[], int n) {
for (int i = 1; i < n; i++) {
Item key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].value >= key.value) { /* BUG: >= breaks stability */
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main(void) {
Item arr[] = { {5, 'A'}, {3, 'B'}, {5, 'C'}, {2, 'D'} };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSortUnstable(arr, n);
for (int i = 0; i < n; i++) {
printf("%d%c ", arr[i].value, arr[i].id);
}
printf("\n");
return 0;
}Output:
2D 3B 5C 5A The two 5s started as A then C, but end up as C then A — their order flipped. Changing the comparison to a strict > stops shifting once an equal element is found, preserving original order:
#include <stdio.h>
typedef struct {
int value;
char id;
} Item;
void insertionSortStable(Item arr[], int n) {
for (int i = 1; i < n; i++) {
Item key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].value > key.value) { /* FIX: strict > preserves order of equals */
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main(void) {
Item arr[] = { {5, 'A'}, {3, 'B'}, {5, 'C'}, {2, 'D'} };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSortStable(arr, n);
for (int i = 0; i < n; i++) {
printf("%d%c ", arr[i].value, arr[i].id);
}
printf("\n");
return 0;
}Output:
2D 3B 5A 5C A now correctly precedes C, matching their original relative order.
Best Practices
- Reach for insertion sort when
nis small (roughly under 20–50 elements) or the data is already mostly sorted — both are its strong suits. - Use a signed integer type (
int, notsize_t) for any index that needs to reach-1, to avoid unsigned underflow bugs. - Keep the comparison strict (
>, not>=) if you need a stable sort — important when sorting records that carry other data besides the sort key. - For large or unpredictable datasets, use a O(n log n) algorithm (merge sort, or the standard library’s
qsort) instead — insertion sort’s O(n2) worst case gets expensive fast. - Many production sorts use insertion sort as the base case for small sub-arrays inside a bigger divide-and-conquer sort (hybrid quicksort/Timsort-style), combining both algorithms’ strengths.
- When shifting large structs, consider
memmovefor the block shift instead of a manual loop if profiling shows the copy is a bottleneck.
Practice Exercises
- Write an
insertionSortDescfunction that sorts an array ofdoublevalues in descending order. Test it on{3.1, 1.4, 1.5, 9.2, 6.5}. - Modify the
insertionSortfunction to count and print the total number of shift operations performed while sorting a given array. Run it on an already-sorted array and a reverse-sorted array of the same size, and compare the counts. - Implement binary insertion sort: instead of scanning linearly to find where
keybelongs, use a binary search on the sorted region to find the insertion index, then shift the elements after it. This reduces comparisons to O(log n) per element, though the number of shifts stays the same.
Summary
- Insertion sort grows a sorted region one element at a time by inserting each new element into its correct position via shifting, not full swaps.
- It runs in O(n) best case (already sorted), O(n2 average and worst case, and uses O(1) extra space — it sorts in place.
- Always use a signed type for indices that need to go negative; an unsigned
size_tindex silently underflows and reads out of bounds. - Use a strict
>comparison to keep the sort stable;>=reverses the order of equal elements. - It’s ideal for small arrays and nearly-sorted data, and is commonly used as the small-array base case inside faster hybrid sorting algorithms.
