Merge sort in C++
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
merge_sort.hpp, 51 lines- Level
- Native tests
- pass in this build
- Toolchain
- C++23, GCC 15 or Clang 21, with ASan and UBSan
- Test framework
- assert
- Run the tests
c++ -std=c++23 -Wall -Wextra -Wpedantic -Werror -fsanitize=address,undefined test_<name>.cpp && ./a.out
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
#pragma once
#include <cstddef>
#include <span>
#include <utility>
#include <vector>
namespace algo {
namespace detail {
template <typename T>
void merge(std::span<T> a, std::size_t mid, std::vector<T>& b) {
b.assign(std::make_move_iterator(a.begin()), std::make_move_iterator(a.begin() + mid)); // @line L6
std::size_t i = 0, j = mid, k = 0; // @line L7
while (i < b.size() && j < a.size()) { // @line L8
if (!(a[j] < b[i])) { // @line L9: b[i] <= a[j], with only <
a[k] = std::move(b[i++]);
} else {
a[k] = std::move(a[j++]); // @line L10
}
k++; // @line L11
}
while (i < b.size()) { // @line L12
a[k++] = std::move(b[i++]); // @line L13
}
}
template <typename T>
void sort(std::span<T> a, std::vector<T>& b) {
if (a.size() <= 1) return; // @line L1
std::size_t mid = a.size() / 2; // @line L2
sort(a.first(mid), b); // @line L3
sort(a.subspan(mid), b); // @line L4
merge(a, mid, b); // @line L5
}
} // namespace detail
// merge_sort sorts a in place, in non-decreasing order. The sort is stable.
template <typename T>
void merge_sort(std::span<T> a) {
std::vector<T> b;
b.reserve((a.size() + 1) / 2);
detail::sort(a, b);
}
} // namespace algo
test_merge_sort.cpp 41 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "merge_sort.hpp"
struct Item {
int key;
char tag;
bool operator<(const Item& o) const { return key < o.key; }
};
int main() {
std::vector<int> a{38, 27, 43, 3, 9, 82, 10};
algo::merge_sort(std::span<int>(a));
assert((a == std::vector<int>{3, 9, 10, 27, 38, 43, 82}));
std::vector<Item> s{{2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}, {2, 'e'}};
algo::merge_sort(std::span<Item>(s));
std::string tags;
for (const auto& x : s) tags += x.tag;
assert(tags == "bdace");
std::mt19937 rng(2150);
for (int t = 0; t < 500; t++) {
std::vector<int> b(rng() % 61);
for (auto& v : b) v = static_cast<int>(rng() % 101) - 50;
auto want = b;
algo::merge_sort(std::span<int>(b));
std::ranges::sort(want);
assert(b == want);
}
std::cout << "ok\n";
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work