Step 1 of 6

Insertion sort

You'll almost always sort with std::sort in real code. But knowing how sorting works teaches the core ideas of algorithm design (growing a solved part, divide and conquer, partitioning), and interviewers love asking about it. This module builds the classic algorithms yourself.

Insertion sort grows a sorted prefix, like sorting cards in your hand: take the next card and slide it left past every larger card until its spot opens up.

for i in 1..n-1:
    key = v[i]; j = i - 1
    while j >= 0 and v[j] > key: v[j + 1] = v[j]; j--
    v[j + 1] = key

#include <iostream>
#include <string>
#include <vector>

void show(const std::vector<std::string>& v) {
    for (const auto& s : v) std::cout << s << " ";
    std::cout << "\n";
}

int main() {
    std::vector<std::string> hand = {"7", "3", "9", "2"};
    show(hand);
    for (std::size_t i = 1; i < hand.size(); i++) {
        std::string key = hand[i];
        int j = (int)i - 1;
        while (j >= 0 && std::stoi(hand[j]) > std::stoi(key)) {
            hand[j + 1] = hand[j];          // shift the bigger card right
            j--;
        }
        hand[j + 1] = key;                  // drop the key into the gap
        show(hand);
    }
}

7 3 9 2 
3 7 9 2 
3 7 9 2 
2 3 7 9 

Reading the trace

• Step 1: 3 is smaller than 7, so 7 shifts right and 3 goes first.
• Step 2: 9 is bigger than everything before it, so nothing moves.
• Step 3: 2 is smaller than all three, so all three shift and 2 lands at the front.

The part to the left of i is always sorted, and each step makes it one longer.

Properties

• O(n²) in general, but O(n) on data that's already almost sorted, because each element only shifts a little.
• Stable (equal elements keep their order) and in place (no extra array).
• Fastest of all for tiny arrays. Real std::sort implementations switch to it for ranges below about 16 elements.

The number of shifts equals the number of pairs that are out of order (called inversions), which is why it measures how unsorted the input was.

Your turn: implement insertion_sort and return how many element shifts it performed (a measure of how unsorted the input was).

Next: Merge sort