Insertion sort, step by step

Everything left of i is already sorted. key is the next element; larger elements shift one box right to make room, and key drops into the gap. Watch the array settle one element at a time.

#include <stdio.h>

int main(void) {
    int a[5] = {5, 2, 4, 1, 3};
    for (int i = 1; i < 5; 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("%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4]);
    return 0;
}

Output:

1 2 3 4 5

From the lesson: Sorting algorithms