patterncMinor

Mergesort that has `man 3 qsort` ANSI C prototype

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

mergesortansihasqsortthatprototypeman

Problem

I have taken a look at these review questions: one, two, three and four and would still like to ask you to review my implementation of mergesort that follows the man 3 qsort prototype.

void *malloc_or_exit(size_t size) {
    void *tmp = malloc(size);

    if (tmp == NULL) {

        if (size == 0) {
            return tmp;
        }

        fprintf(
            stderr, "Failed to malloc %zu bytes: %s",
            size, strerror(errno)
        );

        exit(EXIT_FAILURE);
    }

    return tmp;
}

void mergesort0(
    void *xs, size_t n, size_t s,
    int (*cmp) (const void *, const void *)
) {
    if (n == 0 || n == 1) return;

    const size_t nlft = n / 2;
    const size_t nrgt = n - nlft;

    void *ys = (char *)xs + nlft * s;

    mergesort0(xs, nlft, s, cmp);
    mergesort0(ys, nrgt, s, cmp);

    void *const as = malloc_or_exit(n * s);
    void *const bs = (char *)as + nlft * s;
    void *const cs = (char *)as + n * s;

    memcpy(as, xs, n * s);

    void const *i = as;
    void const *j = bs;
    while (i != bs && j != cs) {
        if (cmp(i, j) 
int main() {
    int xs[] = {1, 2, 3, 4, 5};
    int ys[] = {5, 4, 3, 2, 1};
    int zs[] = {3, 1, 2, 4, 5};
    int as[] = {1, 1, 1};
    int bs[] = {3, 2, 2};

    int len = 5;

    qsort(zs, len, sizeof(int), compare_int);

    for (int i = 0; i < len; ++i) {
        printf("%d ", *(zs + i));
    } printf("\n");
}

Solution

-
Better show your includes too, that makes evaluating your code easier and more meaningful.

Anyway, it's `, and

.

- 
You know you can combine multiple conditions into a single expression with

?

- 
You can avoid all those casts if you use

char instead of void

 internally.

- 
Why don't you reuse a single allocation instead of doing n*log(n) ones, each local?

- 
You know doing a single combined

memcpy

 is far more efficient than multiple consecutive smaller ones?

- 
If you only move the first

nlft` elements out of the way, you only need half the extra-space and save on copying.

Your test-program:

-
Your test-program doesn't seem to exercise your code...

-
You lost a newline at the end of your test-program.

Modified code:

#include 
#include 
#include 

void* malloc_or_exit(size_t size) {
    void* result = malloc(size);

    if (!result && size) {
        fprintf(
            stderr, "Failed to malloc %zu bytes: %s",
            size, strerror(errno)
        );
        exit(EXIT_FAILURE);
    }

    return result;
}

static void mergesort0_impl(
    char* as, char* xs, size_t n, size_t s,
    int (*cmp) (const void*, const void*)
) {
    if (n 

void test(int nr, const int xs[], size_t n) {
    int* a = malloc_or_exit(2 * n * sizeof *xs);
    int* b = a + n;
    memcpy(a, xs, n * sizeof *xs);
    memcpy(b, xs, n * sizeof *xs);
    qsort(a, n, sizeof *a, compare_int);
    mergesort0(b, n, sizeof *b, compare_int);
    printf("Test %d %s: ", nr, !memcmp(a, b, n * sizeof *xs) ? "OK" : "FAILED");
    for (size_t i = 0; i < n; ++i)
        printf("%d%c", xs[i], " \n"[i == n - 1]);
    free(a);
}

int main() {
    int xs[] = {1, 2, 3, 4, 5};
    int ys[] = {5, 4, 3, 2, 1};
    int zs[] = {3, 1, 2, 4, 5};
    int as[] = {1, 1, 1};
    int bs[] = {3, 2, 2};
    int nr = 0;
    #define TEST(a) test(nr++, a, sizeof a / sizeof *a)
    TEST(xs);
    TEST(ys);
    TEST(zs);
    TEST(as);
    TEST(bs);
    #undef TEST
}

Code Snippets

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void* malloc_or_exit(size_t size) {
    void* result = malloc(size);

    if (!result && size) {
        fprintf(
            stderr, "Failed to malloc %zu bytes: %s",
            size, strerror(errno)
        );
        exit(EXIT_FAILURE);
    }

    return result;
}

static void mergesort0_impl(
    char* as, char* xs, size_t n, size_t s,
    int (*cmp) (const void*, const void*)
) {
    if (n < 2) return;

    const size_t nlft = n / 2;
    const size_t nrgt = n - nlft;

    char* ys = xs + nlft * s;

    mergesort0_impl(as, xs, nlft, s, cmp);
    mergesort0_impl(as, ys, nrgt, s, cmp);

    char* const bs = as + nlft * s;

    memcpy(as, xs, nlft * s);

    const char* i = as;
    const char* j = ys;
    for (; i != bs && j != xs; xs += s) {
        if (cmp(i, j) <= 0) {
            memcpy(xs, i, s);
            i += s;
        } else {
            memcpy(xs, j, s);
            j += s;
        }
    }
    if (i != bs)
        memcpy(xs, i, bs - i);
}

void mergesort0(
    void* xs, size_t n, size_t s,
    int (*cmp) (const void*, const void*)
) {
    if(n < 2) return;
    void* as = malloc_or_exit(n / 2 * s);
    mergesort0_impl(as, xs, n, s, cmp);
    free(as);
}


#include <stdio.h>

void test(int nr, const int xs[], size_t n) {
    int* a = malloc_or_exit(2 * n * sizeof *xs);
    int* b = a + n;
    memcpy(a, xs, n * sizeof *xs);
    memcpy(b, xs, n * sizeof *xs);
    qsort(a, n, sizeof *a, compare_int);
    mergesort0(b, n, sizeof *b, compare_int);
    printf("Test %d %s: ", nr, !memcmp(a, b, n * sizeof *xs) ? "OK" : "FAILED");
    for (size_t i = 0; i < n; ++i)
        printf("%d%c", xs[i], " \n"[i == n - 1]);
    free(a);
}

int main() {
    int xs[] = {1, 2, 3, 4, 5};
    int ys[] = {5, 4, 3, 2, 1};
    int zs[] = {3, 1, 2, 4, 5};
    int as[] = {1, 1, 1};
    int bs[] = {3, 2, 2};
    int nr = 0;
    #define TEST(a) test(nr++, a, sizeof a / sizeof *a)
    TEST(xs);
    TEST(ys);
    TEST(zs);
    TEST(as);
    TEST(bs);
    #undef TEST
}

Context

StackExchange Code Review Q#163379, answer score: 5

Revisions (0)

No revisions yet.