Insertion Sort & Merge Sort — 2 Examples
0%
Sorting Algorithms  ·  2 Examples

Insertion Sort &
Merge Sort in C

Two fundamental sorting algorithms — one that builds a sorted hand card by card, and one that divides, conquers, and merges — each with a full step-by-step trace.

1
Insertion Sort
2
Merge Sort
1
🃏 Insertion Sort — Build Sorted Hand Card by Card
Pick one element at a time and slide it into the correct position in the sorted prefix
O(n²) / O(n)
Insertion Sort works exactly like sorting a hand of playing cards. You maintain a sorted prefix on the left. For each new element (the key), you shift larger sorted elements one position to the right until you find the correct slot, then insert the key there. The sorted prefix grows by one each pass until the whole array is sorted. Best case is O(n) — already sorted input requires zero shifts. Worst case is O(n²) — reverse-sorted input shifts every element every pass. Space: O(1) — entirely in-place. It is stable and the fastest algorithm in practice for small arrays (n ≤ 20) or nearly-sorted data.
insertion_sort.c
C
#include <stdio.h>

void printPass(int pass, int key, int *arr, int n) {
    printf("  Pass %2d  key=%2d  [ ", pass, key);
    for (int i = 0; i < n; i++) printf("%2d ", arr[i]);
    printf("]\n");
}

void insertionSort(int *arr, int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];   /* element to be placed */
        int j   = i - 1;

        /* Shift elements greater than key one position right */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  /* insert key in correct slot */

        printPass(i, key, arr, n);
    }
}

int main() {
    int arr[] = { 8, 3, 11, 1, 6, 14, 4, 9 };
    int n     = sizeof(arr) / sizeof(arr[0]);

    printf("=== Insertion Sort ===\n");
    printf("  Input  :  [ ");
    for (int i = 0; i < n; i++) printf("%2d ", arr[i]);
    printf("]\n\n");

    printf("  Pass    key   Array after insertion\n");
    printf("  %-----------------------------------------\n");
    insertionSort(arr, n);

    printf("\n  Sorted  :  [ ");
    for (int i = 0; i < n; i++) printf("%2d ", arr[i]);
    printf("]\n");
    return 0;
}
output
=== Insertion Sort ===
  Input  :  [  8  3 11  1  6 14  4  9 ]

  Pass    key   Array after insertion
  -----------------------------------------
  Pass  1  key= 3  [  3  8 11  1  6 14  4  9 ]
  Pass  2  key=11  [  3  8 11  1  6 14  4  9 ]
  Pass  3  key= 1  [  1  3  8 11  6 14  4  9 ]
  Pass  4  key= 6  [  1  3  6  8 11 14  4  9 ]
  Pass  5  key=14  [  1  3  6  8 11 14  4  9 ]
  Pass  6  key= 4  [  1  3  4  6  8 11 14  9 ]
  Pass  7  key= 9  [  1  3  4  6  8  9 11 14 ]

  Sorted  :  [  1  3  4  6  8  9 11 14 ]
pass-by-pass trace — sorted prefix grows from left, key slides left until placed
Start
8
3
11
1
6
14
4
9
← unsorted
Pass 1 (3)
3
8
11
1
6
14
4
9
← 3 slid left of 8
Pass 3 (1)
1
3
8
11
6
14
4
9
← 1 shifted all 3 aside
Pass 6 (4)
1
3
4
6
8
11
14
9
← 7 sorted, 1 left
Done
1
3
4
6
8
9
11
14
← fully sorted
Best use case — nearly sorted data. When the array is almost in order, the inner while loop almost never executes — giving near O(n) performance. This is why Timsort (used in Python and Java) switches to Insertion Sort for subarrays smaller than ~32 elements: it is faster than Quick Sort at that scale due to zero overhead and perfect cache locality.
Insertion Sort is stable. The condition arr[j] > key (strict greater-than) means equal elements are never swapped — they stay in their original relative order. Changing > to >= would make it unstable and is a common subtle bug to avoid.
example 2
2
🔀 Merge Sort — Divide, Sort, and Merge
Recursively split the array in half, sort each half, then merge back in order
O(n log n)
Merge Sort is a classic divide-and-conquer algorithm. It recursively splits the array in half until subarrays are of size 1 (trivially sorted), then merges pairs of sorted subarrays back together in the correct order. The merge step is the heart of the algorithm — it compares the front elements of two sorted halves and always picks the smaller one into the output. Time: O(n log n) in all cases — best, average, and worst. Space: O(n) for the temporary merge buffer. It is stable and the algorithm of choice when guaranteed O(n log n) with stability is required — used internally by Python's sorted(), Java's Arrays.sort for objects, and most standard library sort implementations.
merge_sort.c
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int depth = 0;   /* for indented trace */

void printArr(const int *a, int n) {
    printf("[");
    for (int i = 0; i < n; i++)
        printf("%d%s", a[i], i < n-1 ? " " : "");
    printf("]");
}

/* Merge two sorted halves: arr[l..m] and arr[m+1..r] */
void merge(int *arr, int l, int m, int r) {
    int nL = m - l + 1;
    int nR = r - m;

    int *L = (int*)malloc(nL * sizeof(int));
    int *R = (int*)malloc(nR * sizeof(int));

    memcpy(L, arr + l, nL * sizeof(int));
    memcpy(R, arr + m + 1, nR * sizeof(int));

    /* Print what we are merging */
    printf("%*sMerge  ", depth*2, "");
    printArr(L, nL); printf("  +  "); printArr(R, nR);

    int i = 0, j = 0, k = l;
    while (i < nL && j < nR)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < nL) arr[k++] = L[i++];
    while (j < nR) arr[k++] = R[j++];

    printf("  ->  "); printArr(arr + l, r - l + 1); printf("\n");
    free(L); free(R);
}

/* Recursively divide then merge */
void mergeSort(int *arr, int l, int r) {
    if (l >= r) return;          /* base case: single element */
    int m = l + (r - l) / 2;
    depth++;
    printf("%*sSplit  ", depth*2, "");
    printArr(arr + l, r - l + 1);
    printf("  ->  ");
    printArr(arr + l, m - l + 1);
    printf("  |  ");
    printArr(arr + m + 1, r - m);
    printf("\n");
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
    depth--;
}

int main() {
    int arr[] = { 5, 2, 8, 1, 9, 3, 7, 4 };
    int n     = sizeof(arr) / sizeof(arr[0]);

    printf("=== Merge Sort ===\n");
    printf("Input: "); printArr(arr, n); printf("\n\n");

    mergeSort(arr, 0, n - 1);

    printf("\nSorted: "); printArr(arr, n); printf("\n");
    return 0;
}
output
=== Merge Sort ===
Input: [5 2 8 1 9 3 7 4]

  Split  [5 2 8 1 9 3 7 4]  ->  [5 2 8 1]  |  [9 3 7 4]
    Split  [5 2 8 1]  ->  [5 2]  |  [8 1]
      Split  [5 2]  ->  [5]  |  [2]
      Merge  [5]  +  [2]  ->  [2 5]
      Split  [8 1]  ->  [8]  |  [1]
      Merge  [8]  +  [1]  ->  [1 8]
    Merge  [2 5]  +  [1 8]  ->  [1 2 5 8]
    Split  [9 3 7 4]  ->  [9 3]  |  [7 4]
      Split  [9 3]  ->  [9]  |  [3]
      Merge  [9]  +  [3]  ->  [3 9]
      Split  [7 4]  ->  [7]  |  [4]
      Merge  [7]  +  [4]  ->  [4 7]
    Merge  [3 9]  +  [4 7]  ->  [3 4 7 9]
  Merge  [1 2 5 8]  +  [3 4 7 9]  ->  [1 2 3 4 5 7 8 9]

Sorted: [1 2 3 4 5 7 8 9]
divide-and-conquer tree — split down to singles, merge back up
Level 0
5 2 8 1 9 3 7 4
← whole array
Level 1
5 2 8 1
9 3 7 4
← split in half
Level 2
5 2
8 1
9 3
7 4
← pairs
Level 3
5
2
8
1
9
3
7
4
← singles (base case)
Merge up
2 5
1 8
3 9
4 7
← sorted pairs
Final merge
1 2 3 4 5 7 8 9
← sorted
The merge step is O(n) per level and there are O(log n) levels — giving the total O(n log n). Unlike Quick Sort, Merge Sort never degrades: it splits exactly in half every time, guaranteeing log₂ n levels regardless of input order. This predictability makes it the preferred sort for linked lists, external sorting (data larger than RAM), and any situation where worst-case guarantee matters more than average speed.
Merge Sort requires O(n) extra space for the temporary left/right buffers during each merge step. In-place Merge Sort exists but is complex and slow in practice. If O(1) extra space is the constraint and stability is not needed, Heap Sort is the better choice. If both O(n log n) and stability are needed, Merge Sort is the standard answer.
checklist
  • Insertion Sort — pick key = arr[i], shift all arr[j] > key one right, place key in the gap. O(n²) worst, O(n) best (sorted input). O(1) space. Stable. Best for small or nearly-sorted arrays.
  • Merge Sort — split in half recursively until singles, then merge sorted halves by always picking the smaller front element. O(n log n) all cases. O(n) extra space. Stable. Best when guaranteed speed and stability are both required.