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.c, 41 lines- Level
- Native tests
- pass in this build
- Toolchain
- C23, GCC 15 or Clang 21, with ASan and UBSan
- Test framework
- assert
- Run the tests
cc -std=c2x -Wall -Wextra -Wpedantic -Werror -fsanitize=address,undefined *.c && ./a.out
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
#include "merge_sort.h"
#include <stdlib.h>
#include <string.h>
static void merge(int64_t *a, size_t lo, size_t mid, size_t hi, int64_t *b) {
size_t m = mid - lo;
memcpy(b, a + lo, m * sizeof *b); // @line L6
size_t i = 0, j = mid, k = lo; // @line L7
while (i < m && j < hi) { // @line L8
if (b[i] <= a[j]) { // @line L9
a[k] = b[i++];
} else {
a[k] = a[j++]; // @line L10
}
k++; // @line L11
}
while (i < m) { // @line L12
a[k++] = b[i++]; // @line L13
}
}
static void sort(int64_t *a, size_t lo, size_t hi, int64_t *b) {
if (hi - lo <= 1) return; // @line L1
size_t mid = lo + (hi - lo) / 2; // @line L2
sort(a, lo, mid, b); // @line L3
sort(a, mid, hi, b); // @line L4
merge(a, lo, mid, hi, b); // @line L5
}
bool merge_sort(int64_t *a, size_t n) {
if (n <= 1) return true;
int64_t *b = malloc((n + 1) / 2 * sizeof *b);
if (b == NULL) return false;
sort(a, 0, n, b);
free(b);
return true;
}
merge_sort.h 15 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
#ifndef MERGE_SORT_H
#define MERGE_SORT_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
// merge_sort sorts a[0..n-1] in place, in non-decreasing order. The sort is stable.
// It returns false, and does not change a, when it cannot allocate the buffer.
bool merge_sort(int64_t *a, size_t n);
#endif
test_merge_sort.c 34 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "merge_sort.h"
static int cmp(const void *p, const void *q) {
int64_t a = *(const int64_t *)p, b = *(const int64_t *)q;
return (a > b) - (a < b);
}
int main(void) {
int64_t a[] = {38, 27, 43, 3, 9, 82, 10};
const int64_t want[] = {3, 9, 10, 27, 38, 43, 82};
assert(merge_sort(a, 7));
assert(memcmp(a, want, sizeof a) == 0);
assert(merge_sort(NULL, 0));
srand(2150);
int64_t b[60], c[60];
for (int t = 0; t < 500; t++) {
size_t n = (size_t)(rand() % 61);
for (size_t i = 0; i < n; i++) b[i] = c[i] = rand() % 101 - 50;
assert(merge_sort(b, n));
qsort(c, n, sizeof c[0], cmp);
assert(n == 0 || memcmp(b, c, n * sizeof b[0]) == 0);
}
puts("ok");
return 0;
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work