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.cpp
Replay: real traced execution (multi-file project)
#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr{5, 1, 4, 2, 8};
    for (size_t i = 1; i < arr.size(); ++i) {
        int key = arr[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
    std::cout << "[";
    for (size_t i = 0; i < arr.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << arr[i];
    }
    std::cout << "]" << std::endl;
    return 0;
}

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

    1#include <iostream>2#include <vector>
    values this step[5, 1, 4, 2, 8]arr

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

    6for (size_t i = 1; i < arr.size(); ++i) {7    int key = arr[i];8    int j = static_cast<int>(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 = static_cast<int>(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 = static_cast<int>(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]

    1#include <iostream>2#include <vector>
    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

  • In C++, the input is a std::vector<int> initialized as {5, 1, 4, 2, 8} and sorted in place; no second vector is allocated.
  • The outer loop uses size_t i from 1 to arr.size() - 1, while the backward scan uses int j = static_cast<int>(i) - 1 so it can test j >= 0 before reading arr[j].
  • int key = arr[i] copies the current vector element into a scalar temporary before shifts overwrite later slots.
  • The while loop shifts with arr[j + 1] = arr[j] while arr[j] > key, then writes the saved key back with arr[j + 1] = key.
  • The trace records [5, 1, 4, 2, 8], then insertions to [1, 5, 4, 2, 8], [1, 4, 5, 2, 8], and [1, 2, 4, 5, 8]; the final 8 needs no visible shift.
  • Output is streamed with std::cout, a size_t print loop, comma separators, and std::endl, producing [1, 2, 4, 5, 8]. Visible allocation is the vector storage from the initializer list; mutation is limited to vector element assignments and the scalar key/j locals.