Merge Sort

# Merge Sort

Zerethon Official Sample `merge-sort`, version 1.2.0, C++ (GCC 14).

- `merge_sort.cpp` / `merge_sort.hpp` — the algorithm (the same steps as this sample's C code)
- `main.cpp` — entry file: a short demonstration
- `test_merge_sort.cpp` — checks; set it as the entry file to run them (or Run ▾ → Run tests)

Run compiles the entry file together with every other `.cpp` file except other programs (files
whose name starts with `main` or `test_`).

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/merge-sort-visualizer

#include <algorithm>
#include <iostream>
#include <vector>
#include "merge_sort.hpp"

static void print(const char *label, const std::vector<int> &a) {
    std::cout << label << '[';
    for (size_t i = 0; i < a.size(); i++) std::cout << (i ? ", " : "") << a[i];
    std::cout << "]\n";
}

int main() {
    const std::vector<int> numbers = {38, 27, 43, 3, 9, 82, 10, 27};
    print("Before: ", numbers);
    std::vector<int> result = numbers;
    merge_sort(result);
    print("After:  ", result);
    std::vector<int> expected = numbers;
    std::sort(expected.begin(), expected.end());
    std::cout << "Same as std::sort: " << std::boolalpha << (result == expected) << '\n';
}

// Merge Sort (Zerethon Official Sample: merge-sort 1.2.0).
#include "merge_sort.hpp"
#include <utility>

void merge_sort(std::vector<int> &a) {
    if (a.size() <= 1) return;
    const auto mid = a.begin() + a.size() / 2;
    std::vector<int> left(a.begin(), mid), right(mid, a.end());
    merge_sort(left);
    merge_sort(right);
    size_t i = 0, j = 0, k = 0;
    while (i < left.size() && j < right.size()) {
        a[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    }
    while (i < left.size()) a[k++] = left[i++];
    while (j < right.size()) a[k++] = right[j++];
}

// Merge Sort (Zerethon Official Sample: merge-sort 1.2.0).
#pragma once
#include <vector>

void merge_sort(std::vector<int> &a);

// Checks for merge_sort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include "merge_sort.hpp"

// Deterministic pseudo-random integers in [-50, 49] (the same as the other languages' checks).
static std::vector<int> numbers(long long seed, int count) {
    std::vector<int> out;
    for (int i = 0; i < count; i++) {
        seed = (seed * 1103515245LL + 12345LL) % 2147483648LL;
        out.push_back(static_cast<int>(seed % 100) - 50);
    }
    return out;
}

int main() {
    std::vector<std::vector<int>> cases = {{}, {1}, {2, 1}, {1, 2, 3}, {3, 2, 1}, {5, 1, 5, 1, 5}, {-3, 0, -1, 2}};
    for (const auto &[seed, size] : std::vector<std::pair<int, int>>{{1, 10}, {2, 50}, {3, 200}}) cases.push_back(numbers(seed, size));

    for (size_t i = 0; i < cases.size(); i++) {
        std::vector<int> result = cases[i], expected = cases[i];
        merge_sort(result);
        std::sort(expected.begin(), expected.end());
        if (result != expected) {
            std::cerr << "merge_sort: wrong result for case " << i + 1 << " (length " << cases[i].size() << ")\n";
            return 1;
        }
    }
    std::cout << "All " << cases.size() << " checks passed." << std::endl;
}