Insertion sort and merge sort

Two sorts worth knowing by heart, because they sit at opposite corners:

Production sorts are hybrids of exactly these ideas: std::stable_sort is a merge sort that switches to insertion sort for short runs, and Timsort (Python, Java) is "merge runs you find, insertion-sort the short ones".

1. Stability

A sort is stable if elements that compare equal keep their original order. It matters as soon as you sort records by one key:

#include <algorithm>
#include <print>
#include <string>
#include <vector>

struct Order {
    std::string customer;
    int day;
};

int main() {
    // Already in time order. Sort by customer, keeping each customer's orders in time order.
    std::vector<Order> orders{{"bo", 1}, {"ana", 2}, {"bo", 3}, {"ana", 4}, {"cy", 5}};
    std::ranges::stable_sort(orders, {}, &Order::customer);
    for (const auto& o : orders) std::println("{} day {}", o.customer, o.day);
}

std::ranges::sort (introsort) gives no such guarantee: ana 4 may come before ana 2. Stability lets you sort by several keys in sequence: sort by the secondary key, then stable-sort by the primary.

The {}, &Order::customer arguments are the comparator (default std::ranges::less) and a projection: the algorithm compares o.customer, not whole Orders.

2. Insertion sort

Keep a sorted prefix v[0, i). Take v[i] out, slide every element of the prefix that is strictly greater one slot right, and drop v[i] into the gap:

#include <cstddef>
#include <functional>
#include <print>
#include <span>
#include <utility>
#include <vector>

template <class T, class Compare = std::less<>>
void insertion_sort(std::span<T> v, Compare comp = {}) {
    for (std::size_t i = 1; i < v.size(); ++i) {     // invariant: v[0, i) is sorted
        T x = std::move(v[i]);                       // open a gap at i
        std::size_t j = i;
        while (j > 0 && comp(x, v[j - 1])) {         // strictly greater? slide it right
            v[j] = std::move(v[j - 1]);
            --j;
        }
        v[j] = std::move(x);                         // fill the gap
    }
}

int main() {
    std::vector<int> v{8, 3, 5, 1, 4, 9, 2};
    insertion_sort(std::span(v));
    std::println("{}", v);
}

Three properties fall straight out of the inner loop's condition comp(x, v[j - 1]):

• Stable: an element equal to x stops the slide, so x lands after it. Write !comp(v[j - 1], x) (that is, <=) and equal elements get overtaken.
• Adaptive: the work is one comparison per element plus one per inversion (pair out of order). Sorted input: n − 1 comparisons. Reversed: ~n²/2.
• Move-only friendly: it only ever moves elements, never copies.

3. Merge sort

Split in half, sort each half recursively, merge the two sorted halves. All the real work is in the merge:

#include <cstddef>
#include <functional>
#include <print>
#include <span>
#include <utility>
#include <vector>

template <class T, class Compare>
void merge_halves(std::span<T> v, std::size_t mid, std::vector<T>& buf, Compare& comp) {
    buf.clear();
    for (std::size_t i = 0; i < mid; ++i) buf.push_back(std::move(v[i]));  // left half out
    std::size_t i = 0, j = mid, k = 0;      // buf[i], v[j] are the heads; v[k] is the next slot
    while (i < buf.size() && j < v.size()) {
        if (comp(v[j], buf[i])) v[k++] = std::move(v[j++]);   // right strictly smaller
        else                    v[k++] = std::move(buf[i++]); // ties take left: stable
    }
    while (i < buf.size()) v[k++] = std::move(buf[i++]);     // right leftovers are in place
}

template <class T, class Compare>
void merge_sort_rec(std::span<T> v, std::vector<T>& buf, Compare& comp) {
    if (v.size() <= 1) return;
    std::size_t mid = v.size() / 2;
    merge_sort_rec(v.first(mid), buf, comp);
    merge_sort_rec(v.subspan(mid), buf, comp);
    merge_halves(v, mid, buf, comp);
}

template <class T, class Compare = std::less<>>
void merge_sort(std::span<T> v, Compare comp = {}) {
    std::vector<T> buf;
    buf.reserve(v.size() / 2 + 1);   // one buffer for the whole sort; no default constructor needed
    merge_sort_rec(v, buf, comp);
}

int main() {
    std::vector<int> v{5, 2, 7, 1, 5, 6, 9, 0};
    merge_sort(std::span(v));
    std::println("{}", v);
}

Why k never overtakes j: slots v[0, j) are all free (their contents were moved into buf or already moved forward), and k = i + (j − mid) < j while i < mid. So writing v[k] never clobbers an unread right-half element.

Complexity. The recursion has ⌈log₂ n⌉ levels; the merges on one level touch every element once. So O(n log n) time on every input, and O(n) extra space for the buffer (half the elements here). One cheap improvement: if !comp(v[mid], v[mid - 1]) the halves are already in order — skip the merge, and sorted input costs O(n).

Bottom-up variant: no recursion — merge adjacent runs of width 1, then 2, 4, 8, … The same merge routine; it's the natural shape for linked lists and for sorting data that doesn't fit in memory.

Faded example — your turn

Write the bottom-up driver. merge_halves(v.subspan(lo, len), mid, buf, comp) merges the two runs inside a window. What are len and mid for the last, possibly short window?

for (std::size_t width = 1; width < v.size(); width *= 2) {
    for (std::size_t lo = 0; lo + width < v.size(); lo += 2 * width) {
        std::size_t len = /* ??? */;
        merge_halves(v.subspan(lo, len), /* mid = ??? */, buf, comp);
    }
}

4. Comparators: strict weak ordering

Every standard sort (and lower_bound, std::map, …) requires comp to be a strict weak ordering:

1. Irreflexive: comp(a, a) is false. (So <= is never valid.)
2. Transitive: comp(a, b) and comp(b, c) imply comp(a, c).
3. Equivalence is transitive: if a and b are incomparable (neither is less), and so are b and c, then so are a and c.

Break the contract and the behaviour is undefined — not just "a slightly wrong order". std::sort's inner loop relies on the comparator to stop it at the array boundary; with <= on many equal elements it runs off the end:

std::vector<int> v(64, 7);
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });  // out-of-bounds reads

Common ways to break it: <=; comparing floating-point values that include NaN; comparing by a.x < b.x || a.y < b.y (not transitive — use std::tie(a.x, a.y) < std::tie(b.x, b.y) or operator<=>).

5. Which to use

• In real code: std::ranges::sort when order of equals doesn't matter (fast, in-place), std::ranges::stable_sort when it does, both with projections.
• Insertion sort by hand: tiny arrays (n ≲ 16), or data that's nearly sorted — e.g. re-sorting after appending a few elements.
• Merge sort by hand: linked lists (merging needs no buffer there), external sorting, or when you need guaranteed O(n log n) and stability.

Summary

• Insertion sort: sorted-prefix invariant; slide only strictly greater elements; O(n + inversions); stable; no extra space.
• Merge sort: split, recurse, merge with a buffer; ties take the left; O(n log n) always; O(n) space.
• Comparators must be strict weak orderings: <, never <=.
• Sort records by a field with a projection: std::ranges::stable_sort(v, {}, &T::field).