Insertion sort in C and insertion sort in JavaScript use the same key-and-shift procedure. You scan from left to right, keep the items before the current index sorted, and insert each new key into its correct position.
The method is simple, in-place, and stable. The trace below shows exactly how comparisons and shifts produce the sorted result before you see both implementations.
How insertion sort builds a sorted prefix
Insertion sort treats the first element as a sorted prefix. On each pass, it stores the next value as the key, compares that key with values to its left, and shifts larger values one position right. It then writes the key into the open position.
The loop invariant is: before iteration i, positions 0 through i – 1 are sorted and contain the same values as before the iteration. A shift moves a value; it does not discard or swap the key.
Trace one array: keys, comparisons, and shifts
Trace the array [5, 2, 4, 6, 1] from left to right:
- Start with the sorted prefix [5].
- Key 2: compare it with 5, shift 5 right, and insert 2. The prefix becomes [2, 5].
- Key 4: compare it with 5 and shift 5. Compare it with 2, stop because 2 is smaller, and insert 4: [2, 4, 5].
- Key 6: compare it with 5. No shift is needed, so the prefix becomes [2, 4, 5, 6].
- Key 1: compare and shift 6, 5, 4, and 2. Insert 1 at the beginning to get [1, 2, 4, 5, 6].
Insertion sort in C and JavaScript: parallel implementations
Both versions use the same key, j, and shifting loop. The C program prints the result, while the JavaScript function returns the modified array. Neither implementation calls a built-in sort.
C implementation: #include <stdio.h> void insertion_sort(int a[], int n) { for (int i = 1; i < n; 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; } } int main(void) { int values[] = {5, 2, 4, 6, 1}; int n = 5; insertion_sort(values, n); for (int i = 0; i < n; i++) printf(“%d “, values[i]); return 0; }
JavaScript implementation: function insertionSort(values) { for (let i = 1; i < values.length; i++) { const key = values[i]; let j = i – 1; while (j >= 0 && values[j] > key) { values[j + 1] = values[j]; j–; } values[j + 1] = key; } return values; } const values = [5, 2, 4, 6, 1]; console.log(insertionSort(values));
The C output and JavaScript output both contain 1, 2, 4, 5, 6. The comparison uses >, not >=, so equal values remain in their original order.
Complexity and appropriate uses
Insertion sort runs in O(n) time in the best case, when the input is already sorted. Its average and worst-case time are O(n²)O(1) extra space, operates in place, and is stable.
Use it for small arrays, nearly sorted data, or data that arrives incrementally. Each new item can be inserted into the existing sorted prefix immediately. For large, randomly ordered arrays, choose an algorithm with better average performance, such as merge sort or quicksort.