Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C DSA implementation can be compared directly with the other languages.

sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.

Basic Implementation

basic.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

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

  1. arr ← [5, 1, 4, 2, 8]

    1#include <stdio.h>
    values this step[5, 1, 4, 2, 8]arr

  2. arr ← [1, 5, 4, 2, 8]

    6for (int i = 1; i < n; ++i) {7    int key = arr[i];8    int j = i - 1;
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arr1key

  3. arr ← [1, 4, 5, 2, 8]

    8int j = i - 1;9while (j >= 0 && arr[j] > key) {10    arr[j + 1] = arr[j];
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arr4key

  4. arr ← [1, 2, 4, 5, 8]

    8int j = i - 1;9while (j >= 0 && arr[j] > key) {10    arr[j + 1] = arr[j];
    values this step[1, 4, 5, 2, 8] → [1, 2, 4, 5, 8]arr2key

  5. stdout ← [1, 2, 4, 5, 8]

    14}15printf("[");16for (int i = 0; i < n; ++i) {
    values this step[1, 2, 4, 5, 8]stdout[1, 2, 4, 5, 8]arr

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • C stores int arr[] = {5, 1, 4, 2, 8} as a fixed local array in main; this source uses int n = 5 rather than a sizeof length calculation.
  • The outer loop is for (int i = 1; i < n; ++i). Each pass copies arr[i] into the scalar key before any shifts overwrite that slot.
  • int j = i - 1 stays signed so the while (j >= 0 && arr[j] > key) bound can stop before index -1; there is no helper function and no array pointer decay.
  • Shifts mutate the same stack array with arr[j + 1] = arr[j], then arr[j + 1] = key writes the saved value into the opened slot.
  • The trace records [5, 1, 4, 2, 8], then [1, 5, 4, 2, 8], [1, 4, 5, 2, 8], and [1, 2, 4, 5, 8]; the 8 pass does not move.
  • Output is formatted manually with printf("["), comma-separated printf("%d", arr[i]), and printf("]\n"). Visible memory is the stack array plus scalar locals; visible mutation is only the in-place array shifts and key placement.