I'm having issues with getting MergeSort to work in C

Question

I'm having issues with getting my mergeSort algorithm to work properly. The code is below, but I'll briefly summarize what I have tried and what I know is not wrong with the code.

The mergeSort function takes a pointer to an array and the array's size as arguments. If the size of the array is less than 2, it returns immediately. I'm sure that this works, because I debugged this part several times. It returns 8 times, which is what I expected it to do. Next, a variable mid is created as an index to split the array by. I tested it, and I'm pretty confident that mid is correct across all recursions. Then, two arrays are created, the first containing the elements from the indexes 0...mid-1 and the second containing the elements from the indexes mid to n. Next, the sizes of each of these arrays are computed. I tested this too, and the sizes seem correct across all recursions as well. mergeSort is called on the left array and the right array, and then merge is called.

The actual merge function takes a pointer to the original array, a pointer to the left array, a pointer to the right array, and two integer values which are the sizes of each of the left and right arrays. Then, it compares the elements in L and R and copies the smaller of the two into A, in order.

My output, however, is [2] [4] [1] [6] [8] [5] [3] [7] My expected output is: [1] [2] [3] [4] [5] [6] [7] [8]

I'm genuinely not sure why the code isn't working. There's probably something I'm overlooking, but I've been trying to solve it for an hour and figured I'd ask for help.

If you take the time to answer, or attempt to answer this question, thank you for your time. My code is below:

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

void mergeSort(int *, int);
void merge(int *, int *, int, int *, int);
void print(int *, int);

int main() {
    int A[8] = { 2, 4, 1, 6, 8, 5, 3, 7 };
    int arraySize = sizeof(A) / sizeof(A[0]);
    mergeSort(A, arraySize);
    print(A, arraySize);
}

void mergeSort(int *A, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int L[mid];
    int R[n - mid];
    for (int i = 0; i < mid; i++) {
        L[i] = A[i];
    }
    for (int j = mid; j < n; j++) {
        R[j - mid] = A[j + mid + 1];
    }
    int leftSize = sizeof(L) / sizeof(L[0]);
    int rightSize = sizeof(R) / sizeof(R[0]);
    mergeSort(L, leftSize);
    mergeSort(R, rightSize);
    merge(A, L, leftSize, R, rightSize);
}

void merge(int *A, int *L, int leftSize, int *R, int rightSize) {
    int i, j, k;
    while (i < leftSize && j < rightSize) {
        if (L[i] < R[j]) {
            A[k] = L[i];
            k++;
            i++;
        } else {
            A[k] = R[j];
            k++;
            j++;
        }
    }
}

void print(int *A, int n) {
    for (int i = 0; i < n; i++) {
        printf("[%d] ", A[i]);
    }
    printf("\n");
}

`A[j + mid + 1]` will immediately blast past the end of A. `while (i < leftSize && j < rightSize)` ... so once one of them arrives at the end of its half, you give up? What about the rest of the values? `i,j,k` in `merge` are not initialized to anything. — , Jul 16 '21 at 20:27
I suggest you take a a pen and a paper, write down an array of, say, 5 elements and apply your program, as if you are a computer, to this array - writing new array at each step (this is sometimes called paper debugging). At each step, compare what you as a computer produce to results you'd expect. At some point, you will see a deviation - and you should be able to understand what's wrong with the application. — SergeyA, Jul 16 '21 at 20:27
I doubt my quick reading found everything, time for you to [learn to use a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). — , Jul 16 '21 at 20:27
I did what you said and it almost worked (I got: [1][2][3][4][5][5][6][7]! Thank you for your helpful input. I don't think it will be too hard to get the rest of it fixed. The main issue was what you said--I blasted past the end of A. — Anish Sinha, Jul 16 '21 at 20:30

score 0 · Answer 1 · answered Jul 17 '21 at 17:10

There are multiple problems:

the intialization loop for R is incorrect: you should copy A[j] instead of A[j + mid + 1]
the merge function should copy the remaining elements from the left or right arrays once the test i < leftSize && j < rightSize fails.

Here is a modified version:

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

void mergeSort(int *, int);
void merge(int *, int *, int, int *, int);
void print(const int *, int);

int main() {
    int A[8] = { 2, 4, 1, 6, 8, 5, 3, 7 };
    int arraySize = sizeof(A) / sizeof(A[0]);
    mergeSort(A, arraySize);
    print(A, arraySize);
    return 0;
}

void mergeSort(int *A, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int L[mid];
    int R[n - mid];
    for (int i = 0; i < mid; i++) {
        L[i] = A[i];
    }
    for (int j = mid; j < n; j++) {
        R[j - mid] = A[j];
    }
    int leftSize = sizeof(L) / sizeof(L[0]);
    int rightSize = sizeof(R) / sizeof(R[0]);
    mergeSort(L, leftSize);
    mergeSort(R, rightSize);
    merge(A, L, leftSize, R, rightSize);
}

void merge(int *A, int *L, int leftSize, int *R, int rightSize) {
    int i, j, k;
    while (i < leftSize && j < rightSize) {
        if (L[i] <= R[j]) {
            A[k++] = L[i++];
        } else {
            A[k++] = R[j++];
        }
    }
    while (i < leftSize) {
        A[k++] = L[i++];
    }
    while (j < rightSize) {
        A[k++] = R[j++];
    }
}

void print(const int *A, int n) {
    for (int i = 0; i < n; i++) {
        printf("[%d] ", A[i]);
    }
    printf("\n");
}

I'm having issues with getting MergeSort to work in C

1 Answers1