How to create merge sort array using calloc in C language?

I am new to programming and I am stuck on this. I have to edit a file to be able to sort an array. Previously, it was programmed to sort arrays that are powers of two. Now I have to make a change for it to be able to sort arrays of any number. I Could have sworn this worked when I submitted it, but my professor came back and said it doesn't work 🤷‍♀️

I have to use calloc. The other files don't need to be changed. The only change I need to make is in the mergesort.c file and the main.c file that houses the array. I absolutely cannot change the other files so I'm not going to include them but they are correct as I have copied them directly from my text book and have ran them previously for arrays of power 2.

I also previously tried creating an altkey and assigning it the key but he said not to do that..

This is the code in main.c:

#include "mergesort.h"

int main(void) {
    int key[] = { 4, 3, 1, 67, 55, 8, 0, 4, -5, 37, 7, 4, 2, 9, 1 };
    int sz = sizeof(key) / sizeof(int); /* the size of key[]    */

    printf("Before mergesort:\n");
    wrt(key, sz);

    mergesort(key, sz);

    printf("After mergesort:\n");
    wrt(key, sz);
}

This is the current code in mergesort.c:

#include "mergesort.h"

void mergesort(int key[], int n) {
    int j, k, m, *w, i;

    w = calloc(n, sizeof(int)); /* allocate workspace   */
    assert(w != NULL);          /* check that calloc() worked */

    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n - k; j += 2 * k)
            merge(key + j, key + j + k, w + j, k, k);
        for (j = 0; j < n; ++j)
            key[j] = w[j]; /* 11/12/22 write w back into key */
    }

    free(w); /* free the workspace */
}

Merge Function in merge.c (I can't edit this file)

#include "mergesort.h"

void merge(int a[], int b[], int c[], int m, int n) {
    int i = 0, j = 0, k = 0;

    while (i < m && j < n)
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    while (i < m)                   /* pick up any remainder */
        c[k++] = a[i++];
    while (j < n)
        c[k++] = b[j++];
}

Output:

Before mergesort:
4    3    1   67   55    8    0    4   -5   37    7    4    2   9    1
After mergesort:
-5    0    0    1    2    3    4    4    4    7    8    9   15   15   55

Solution

To adapt your bottom-up iterative mergesort function for non powers of 2 lengths, you will need to special case the last pair of slices at each iteration of the outer loop: stop the inner loop whenever there is fewer elements than 2 full slices and merge the last pair of slices if its right half is not empty.

Here is a modified version of your code:

void mergesort(int key[], int n) {
    int i, j, k;
    int *w = calloc(n, sizeof(*w));  /* allocate workspace   */
    assert(w != NULL);          /* check that calloc() worked */

    for (k = 1; k < n; k *= 2) {
        /* merge all the full pairs */
        for (j = 0; j + 2 * k < n; j += 2 * k) {
            merge(key + j, key + j + k, w + j, k, k);
        }
        if (j + k < n) {
            /* merge the last pair if right half is not empty */
            merge(key + j, key + j + k, w + j, k, n - (j + k));
            j = n;
        }
        /* write merged pairs in w back into key */
        for (i = 0; i < j; i++) {
            key[i] = w[i];
        }
    }
    free(w); /* free the workspace */
}

Note also these remarks:

the above code does not achieve an optimal balance of pair lengths: the merge is still performed on slices whose left part's length is a power of 2.
the merge function (which you cannot modify) should declare a and b as const int * and use a test if (a[i] <= b[j]) for better performance on arrays with many duplicates.
the type size_t should be used for the length and index variables.
the write back loop could be omitted in all but the last phase for better performance, using 2 working pointers.

Here is an improved version:

void mergesort(int key[], int n) {
    int i, j, k;
    int *w = calloc(n, sizeof(*w));  /* allocate workspace   */
    assert(w != NULL);          /* check that calloc() worked */

    int *w1 = key;
    int *w2 = w;
    int *w3;

    for (k = 1; k < n; k *= 2) {
        /* merge all the full pairs */
        for (j = 0; j + 2 * k < n; j += 2 * k) {
            merge(w1 + j, w1 + j + k, w2 + j, k, k);
        }
        if (j + k < n) {
            /* merge the last pair if right half is not empty */
            merge(w1 + j, w1 + j + k, w2 + j, k, n - (j + k));
        } else {
            /* copy the left slice of the last pair */
            for (i = j; i < n; i++) {
                w2[i] = w1[i];
        }
        /* swap the working pointers */
        w3 = w2;
        w2 = w1;
        w1 = w3;
    }
    /* write w back to key if needed */
    if (w1 == w) {
        for (i = 0; i < j; i++) {
            key[i] = w[i];
        }
    }
    free(w); /* free the workspace */
}