C++ · DSA: sorting

I implemented two sorts to understand them before relying on the library:

• Insertion sort: take each element and slide it left into place. It’s O(n²) in the worst case, but simple and fast on tiny or nearly sorted arrays.
• Merge sort: split in half, sort each half recursively, then merge. It’s O(n log n) every time, and stable (equal keys keep their order), at the cost of extra memory.

std::sort guarantees O(n log n) comparisons but is not stable. std::stable_sort is. Stability matters when sorting by one key after another, for example by marks and then by name.

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

void insertionSort(std::vector<int>& a) {
    for (std::size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        std::size_t j = i;
        while (j > 0 && a[j - 1] > key) { a[j] = a[j - 1]; --j; }
        a[j] = key;
    }
}

void mergeSort(std::vector<int>& a, std::vector<int>& tmp, std::size_t lo, std::size_t hi) {
    if (hi - lo < 2) return;
    std::size_t mid = lo + (hi - lo) / 2;
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid, hi);
    std::merge(a.begin() + lo, a.begin() + mid, a.begin() + mid, a.begin() + hi, tmp.begin() + lo);
    std::copy(tmp.begin() + lo, tmp.begin() + hi, a.begin() + lo);
}

int main() {
    std::mt19937 rng(42);
    std::vector<int> data(2000);
    for (int& x : data) x = rng() % 10000;

    auto a = data, b = data, c = data;
    insertionSort(a);
    std::vector<int> tmp(b.size());
    mergeSort(b, tmp, 0, b.size());
    std::sort(c.begin(), c.end());
    std::cout << "all equal: " << (a == b && b == c) << ", sorted: " << std::is_sorted(a.begin(), a.end()) << '\n';
    std::cout << "first five: " << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << c[3] << ' ' << c[4] << '\n';

    std::vector<std::pair<int, char>> recs{{2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}};
    std::stable_sort(recs.begin(), recs.end(), [](auto& x, auto& y) { return x.first < y.first; });
    for (auto& [k, v] : recs) std::cout << k << v << ' ';
    std::cout << " (stable: b before d, a before c)\n";
}

Output:

all equal: 1, sorted: 1
first five: 4 7 10 16 16
1b 1d 2a 2c  (stable: b before d, a before c)