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);
    }
}

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 task

Implement insertion_sort and return how many element shifts it performed (a measure of how unsorted the input was).

Challenge 2

Write int selection_sort(std::vector<int>& v): for each position, find the smallest remaining element and swap it into place. Return how many swaps it made, counting only swaps where the smallest element wasn't already in place.

Challenge 3

Write void sort_words(std::vector<std::string>& w) with insertion sort, ordering by length first and alphabetically among words of the same length. Put the comparison in a small helper bool before(const std::string& a, const std::string& b).

Next: Merge sort