Insertion sort in C

Sorting in place by growing a sorted prefix.

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

How it works

1. Each key is lifted out of the array.
2. Larger elements shift right to make room.
3. The key drops into its sorted position.

Keywords and builtins used here

• for
• insertion_sort
• int
• void
• while

The run, in numbers

Lines

11

Characters to type

196

Tokens

86

Three-star pace

95 tpm

At the three-star pace of 95 tokens a minute, this run takes about 54 seconds.

Type this snippet

Step 2 of 5 in Sorting & searching, step 2 of 20 in Data structures & algorithms.

← Previous Next →