Merge Sort

# Merge Sort

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

- `merge_sort.c` / `merge_sort.h` — the algorithm, as shown in Zerethon Tools
- `main.c` — entry file: a short demonstration
- `test_merge_sort.c` — checks; set it as the entry file to run them

Run compiles the entry file together with every other `.c` 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "merge_sort.h"

static void print_array(const char *label, const int *a, int n) {
    printf("%s[", label);
    for (int i = 0; i < n; i++) printf(i ? ", %d" : "%d", a[i]);
    printf("]\n");
}

static int compare(const void *x, const void *y) {
    return (*(const int *) x > *(const int *) y) - (*(const int *) x < *(const int *) y);
}

int main(void) {
    int numbers[] = {38, 27, 43, 3, 9, 82, 10, 27};
    int n = sizeof numbers / sizeof numbers[0];
    int result[sizeof numbers / sizeof numbers[0]], expected[sizeof numbers / sizeof numbers[0]];

    print_array("Before: ", numbers, n);
    memcpy(result, numbers, sizeof numbers);
    merge_sort(result, 0, n - 1);
    print_array("After:  ", result, n);
    memcpy(expected, numbers, sizeof numbers);
    qsort(expected, n, sizeof expected[0], compare);
    printf("Same as qsort(): %s\n", memcmp(result, expected, sizeof result) == 0 ? "true" : "false");
    return 0;
}

/* Merge Sort (Zerethon Official Sample: merge-sort 1.2.0).
   The algorithm as shown in Zerethon Tools. */
#include "merge_sort.h"

void merge_sort(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);
    int n = hi - lo + 1, tmp[n], i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = 0; k < n; k++) a[lo + k] = tmp[k];
}

/* Merge Sort (Zerethon Official Sample: merge-sort 1.2.0). */
#ifndef MERGE_SORT_H
#define MERGE_SORT_H

void merge_sort(int a[], int lo, int hi);

#endif

// 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "merge_sort.h"

static int compare(const void *x, const void *y) {
    return (*(const int *) x > *(const int *) y) - (*(const int *) x < *(const int *) y);
}

/* Deterministic pseudo-random integers in [-50, 49] (the same as the Python checks). */
static void numbers(long long seed, int count, int *out) {
    for (int i = 0; i < count; i++) {
        seed = (seed * 1103515245LL + 12345LL) % 2147483648LL;
        out[i] = (int) (seed % 100) - 50;
    }
}

static int checks = 0;

static int check(const int *c, int n) {
    int result[200], expected[200];
    memcpy(result, c, n * sizeof c[0]);
    memcpy(expected, c, n * sizeof c[0]);
    merge_sort(result, 0, n - 1);
    qsort(expected, n, sizeof expected[0], compare);
    checks++;
    if (memcmp(result, expected, n * sizeof c[0]) != 0) {
        fprintf(stderr, "merge_sort: wrong result for case %d (length %d)\n", checks, n);
        return 0;
    }
    return 1;
}

int main(void) {
    int ok = 1;
    ok &= check((int[]) {0}, 0);
    ok &= check((int[]) {1}, 1);
    ok &= check((int[]) {2, 1}, 2);
    ok &= check((int[]) {1, 2, 3}, 3);
    ok &= check((int[]) {3, 2, 1}, 3);
    ok &= check((int[]) {5, 1, 5, 1, 5}, 5);
    ok &= check((int[]) {-3, 0, -1, 2}, 4);
    int random[200];
    numbers(1, 10, random);
    ok &= check(random, 10);
    numbers(2, 50, random);
    ok &= check(random, 50);
    numbers(3, 200, random);
    ok &= check(random, 200);

    if (!ok) return 1;
    printf("All %d checks passed.\n", checks);
    return 0;
}