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

  • Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
  • The implementation is intentionally compact for learning and replay, not a production sorting utility.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.