mergesort algorithm merge function doesnt work

Question

I am trying to make my own version of mergesort, however, I am kind of stuck on how to merge two array back into a single array with a sequenced order.

Below is my code, after I try to run the programme, some number that does not make sense to me pop up, like 776247896 327641 57752310.

Can anyone tell me what is going wrong with my code? Please enlighten me. Thank you very much.

//nL is the length of left[]
//nR is the length of right[]
//nA is the length of A[]

void merge(int left[], int nL, int right[], int nR, int A[], int nA) {
    int temp[nA];
    
    int i = 0, j = 0, k = 0;
    
    while (i < nL && j < nR) {
        if (left[i] <= right[j]) {
            temp[k++] = left[i++];
        }
        else if (left[i] > right[j]) {
            temp[k++] = right[j++];
        }
    }
    
    while (i == nL && j < nR && k < nA) {
        temp[k++] = right[j++];
    }
    while (j == nR && i < nL && k < nA) {
        temp[k++] = left[i++];
    }
    
    for (int m = 0; m < nA; m++) {
        temp[m] = A[m];
    }
}

int main(void) {
    int left[4] = { 13, 22, 25, 60};
    int right[4] = { 9, 11, 27, 55};
    int sorted[8];
    
    merge(left, 4, right, 4, sorted, 8);
    
    for (int i = 0; i < 8; i++) {
        printf("%i\n", sorted[i]);
    }
}

Answer 1

The final loop in the merge function does not copy from temp back to A, but the other way around. It should be changed to:

    for (int m = 0; m < nA; m++) {
        A[m] = temp[m];
    }

Note also these remarks:

• the length of the destination array should be the sum of the lengths of the left and right arrays, no need to specify it.

• the test else if (left[i] > right[j]) is redundant, it should be removed.

• the test while (i == nL && j < nR && k < nA) is also redundant: at the end of the first loop, either i == nL or j == nR or both. You could simply write while (j < nR) and the following loop can be simplified too.

Here is a modified version:

#include <stdio.h>

//nL is the length of left[]
//nR is the length of right[]
//nA is the length of A[]

void merge(int left[], int nL, int right[], int nR, int A[]) {
    int temp[nL + nR];
    
    int i = 0, j = 0, k = 0;
    
    while (i < nL && j < nR) {
        if (left[i] <= right[j]) {
            temp[k++] = left[i++];
        } else {
            temp[k++] = right[j++];
        }
    }
    
    while (i < nL) {
        temp[k++] = left[i++];
    }
    while (j < nR) {
        temp[k++] = right[j++];
    }
    
    for (int m = 0; m < k; m++) {
        A[m] = temp[m];
    }
}

int main(void) {
    int left[4] = { 13, 22, 25, 60};
    int right[4] = { 9, 11, 27, 55};
    int sorted[8];
    
    merge(left, 4, right, 4, sorted);
    
    for (int i = 0; i < 8; i++) {
        printf("%i\n", sorted[i]);
    }
}