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.

Basic Implementation

basic.cpp 
#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;
}

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.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.