Insertion Sort in C: Program, Dry Run and Complexity

Insertion sort in C grows a sorted prefix of an array. For each new element, it saves the element as a key, shifts larger elements one position to the right, and inserts the key into the gap. The iterative version below sorts in ascending order, is stable, and uses constant extra space. It is useful for learning sorting logic and for small or nearly sorted inputs; it is not generally the best choice for large, randomly ordered arrays.

Complete insertion sort program

The example sorts {64, 34, 25, 12, 22}. Each input value fits in int. No stdin is needed: edit the array initializer to try another case, then use the run link below the program. The function accepts an array and its element count; it does not calculate array length from a pointer.

#include <stdio.h>
#include <stddef.h>

void insertion_sort(int values[], size_t count) {
    for (size_t i = 1; i < count; ++i) {
        int key = values[i];
        size_t j = i;

        while (j > 0 && values[j - 1] > key) {
            values[j] = values[j - 1];
            --j;
        }
        values[j] = key;
    }
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];

    insertion_sort(values, count);
    for (size_t i = 0; i < count; ++i) {
        printf("%s%d", i == 0 ? "" : " ", values[i]);
    }
    putchar('\n');
    return 0;
}

12 22 25 34 64

The original array is modified in place. Callers must supply at least count accessible, writable elements. With count == 0, the function performs no access, so a null pointer is permitted for that zero-length call. With a positive count, a null pointer is invalid. To try negative or duplicate values in the displayed program, replace the initializer with {3, -1, 3, 0}; the output should be -1 0 3 3.

Algorithm and loop logic

1. Treat the first element as an already sorted prefix.
2. Starting at index 1, save the next element in key.
3. Move left through the sorted prefix, shifting each element greater than key to the right.
4. Place key in the gap.
5. Repeat until the prefix covers the entire array.

At the start of each outer-loop pass, elements before i are sorted. After insertion, elements through i are sorted. This loop invariant explains why the whole array is sorted when the outer loop finishes; it is more useful than memorizing the code without understanding it.

The inner-loop condition checks j > 0 before evaluating values[j - 1]. C evaluates && left to right and short-circuits the right operand when the left is false. That order prevents j - 1 from wrapping around when j is an unsigned size_t equal to zero. Do not write j >= 0 for an unsigned index: it is always true.

Start with i = 1
      |
      v
Is i < count? -- no --> sorted; stop
      | yes
      v
Save key = values[i], j = i
      |
      v
j > 0 and previous value > key?
      | yes                    | no
      v                        v
Shift previous value       Store key at j
one place right; j--           |
      |                        v
      +-- repeat check       i++; next pass

Dry run: all four passes

The vertical bar below separates the sorted prefix from the remaining input. These are the states after each outer-loop pass, not after each individual assignment.

On the last pass, the key is 22. First 64 moves to index 4, then 34 to index 3, then 25 to index 2. The comparison with 12 stops the shifting. The key goes into index 1. Saving key before shifting is essential: otherwise an assignment can overwrite the value you are trying to insert.

Time complexity and extra space

In reverse order, the number of shifts is 1 + 2 + ... + (n - 1), or n(n - 1) / 2. Nearly sorted input with few inversions needs relatively few shifts, which is why insertion sort can be useful inside hybrid sorting algorithms. “Nearly sorted” is not a blanket promise of linear time for every input someone might describe that way.

For larger datasets, compare merge sort, which guarantees O(n log n) time with extra buffer storage, and quick sort, whose typical performance is good but whose naive pivot choices can cause quadratic worst cases. Choose according to the data and memory constraints rather than a claim that one algorithm is always fastest.

Why this version is stable

A stable sort preserves the original relative order of equal keys. Imagine two records labeled 2a and 2b, both with numeric key 2, in the input 2a 1 2b. Sorting produces 1 2a 2b. When 2b is inserted, the earlier 2a is not shifted because the comparison is strictly greater than, not greater than or equal to.

The labels are explanatory identities, not C integer literals. The program sorts integers, but the same strict comparison is the important rule when adapting it to records. Changing values[j - 1] > key to values[j - 1] >= key can reverse equal records and lose stability. For descending order, use a strictly less-than comparison instead; stability still requires leaving equal keys in order.

Edge cases and common mistakes

• Zero elements: the outer loop never starts. Do not declare a zero-length C array to demonstrate this; standard C does not allow that. A caller can pass a count of zero.
• One element: already sorted; no movement is needed.
• Duplicate and negative values: normal integer comparisons handle both. The algorithm makes no assumption that values are positive or distinct.
• Wrong length: sizeof values / sizeof values[0] works in the scope where values is an actual array. An array parameter in a function is adjusted to a pointer, so the function needs the separate count.
• Off-by-one reads: check the index before accessing the previous element, and start the outer pass at 1 rather than 0.
• Large input: this quadratic method may be too slow. Do not confuse sorting correctness with performance suitability.

Review arrays in C if the count and indexing rules are unfamiliar. The structure lesson explains how the sorting function, header declarations and main fit together.

Practice before running

Predict every pass for {5, 2, 4, 2}. Your final output should be 2 2 4 5; the second 2 should remain after the first 2 when identities are tracked. Then sort an already sorted input and count the shifts: there should be none. Finally, change the comparison for descending order and explain what invariant the prefix now satisfies.

Frequently asked questions

Is insertion sort the same as selection sort?

No. Insertion sort places each next item inside a sorted prefix, shifting larger items. Selection sort repeatedly finds a smallest remaining item and places it at the next position. They can both have quadratic running time but perform different operations and have different stability properties.

Does insertion sort need a sorted array as input?

No. It builds the sorted region itself. In contrast, binary search requires sorted input for its elimination rule to work. If you only need to locate a value once in an unsorted array, linear search may avoid unnecessary sorting.

Can I run this without installing GCC?

Yes. Each run link opens the exact displayed source in the online C compiler. Expected output on this page is a reference; it does not mean your edited program has already executed. Compile locally with gcc -std=c17 -Wall -Wextra -pedantic insertion.c -o insertion if you prefer a local toolchain.