Critical error detected c0000374. MergeSort.exe has triggered a breakpoint

Question

I was trying to implement merge sort in C.

But when I test the code I encounter this error c0000374 in my merge sort function when I try to split array into left right array.

The code is as follows.

typedef struct EntryStruct {
    int data;
    char *name;
} Entry;

typedef char *String;

void merge(Entry *output, Entry *L, int nL, Entry *R, int nR) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (k < nL + nR) {
        if ((L[i].data != NULL && L[i].data < R[i].data) || R[j].data == NULL) {
            output[k] = L[i];
            i++;
        } else {
            output[k] = R[j];
            j++;
        }
        k++;
    }
}

void merge_sort(Entry *entries, int n) {
    if (n > 1) {
        int mid = n / 2;
        Entry *temp = (Entry *)malloc(n * sizeof(Entry));
        Entry *left = (Entry *)malloc(mid * sizeof(Entry));
        Entry *right = (Entry *)malloc((n - mid) * sizeof(Entry));

        for (int l = 0; l < mid; l++)
            left[l] = entries[l];

        for (int r = mid; r < n; r++)
            right[r] = entries[r];

        merge_sort(left, mid);
        merge_sort(right, n - mid);
        merge(temp, left, mid, right, n - mid);
        for (int i = 0 ; i < n; i++) {
            entries[i] = temp[i];
        }
        free(temp);
    }
}

Entry Entry_create(int data, String name) {
    Entry node;
    node.name = (String)malloc(strlen(name) + 1);
    strcpy(node.name, name);
    node.data = data;
    return node;
}

void printArrByName(Entry *arr, int s) {
    for (int i = 0; i < s; i++) {
        printf("%s\n", arr[i].name);
    }
}

int main(void) {
    Entry *arr = malloc(5 * sizeof(*arr));
    arr[0] = Entry_create(5, "abc");
    arr[1] = Entry_create(6, "def");
    arr[2] = Entry_create(2, "ghijk");
    arr[3] = Entry_create(3, "ksdljf");
    arr[4] = Entry_create(1, "lsdfjl");
    merge_sort(arr, 5);
    printArrByName(arr, 5);
    free(arr);
}

I want to ask what is the cause of this problem in my case and how to solve it.

Is this happen because I split array in to left right in the wrong way or is it something to do with the initialization of the array.

Answer 1

There are multiple problems in the code causing undefined behavior:

• [major: undefined behavior] In the merge_sort function, the loop for (int r = mid; r < n; r++) right[r] = entries[r]; accesses the array pointed to by right beyond the end. You should write:

  for (int r = mid; r < n; r++)
      right[r - mid] = entries[r];
  

  This bug is a good candidate to explain the observed behavior as it corrupts the malloc() internal data, causing a subsequent call to malloc() to crash.

• [major: memory leak] You do not free left, nor right. As a matter of fact, allocating copies of the left and right parts of the array is not even necessary.

• [major: undefined behavior] In the merge function, you do not test if i is less than nL, nor of j is less than nR before accessing L[i] or R[j]. Testing if the data member is not NULL does not suffice, accessing an element beyond the end of an array has undefined behavior.

• [minor: unstable sort] L[i].data < R[i].data might not preserve the order of entries that have the same data value. You should use L[i].data <= R[i].data to implement stable sorting.

• [hint] Defining typedef char *String; is a bad idea. Do not hide pointers behind typedefs, it is confusing and error prone.

Here is a modified version:

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

typedef struct EntryStruct {
    int data;
    char *name;
} Entry;

#ifdef _MSC_VER
// define strdup on legacy systems
char *strdup(const char *s) {
    size_t len = strlen(s);
    char *p = (char *)malloc(len + 1);
    if (p)
        memcpy(p, s, len + 1);
    return p;
}
#endif

void merge(Entry *output, Entry *L, int nL, Entry *R, int nR) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (k < nL + nR) {
        if (i < nL && (j >= nR || L[i].data <= R[j].data)) {
            output[k] = L[i];
            i++;
        } else {
            output[k] = R[j];
            j++;
        }
        k++;
    }
}

void merge_sort(Entry *entries, int n) {
    if (n > 1) {
        int mid = n / 2;
        Entry *temp;
        Entry *left = entries;
        Entry *right = entries + mid;

        merge_sort(left, mid);
        merge_sort(right, n - mid);
        temp = (Entry *)malloc(n * sizeof(Entry));
        merge(temp, left, mid, right, n - mid);
        for (int i = 0; i < n; i++) {
            entries[i] = temp[i];
        }
        free(temp);
    }
}

Entry Entry_create(int data, const char *name) {
    Entry node;
    node.name = strdup(name);
    node.data = data;
    return node;
}

void printArrByName(Entry *arr, int n) {
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i].name);
    }
}

int main(void) {
    Entry *arr = malloc(5 * sizeof(*arr));
    arr[0] = Entry_create(5, "abc");
    arr[1] = Entry_create(6, "def");
    arr[2] = Entry_create(2, "ghijk");
    arr[3] = Entry_create(3, "ksdljf");
    arr[4] = Entry_create(1, "lsdfjl");
    merge_sort(arr, 5);
    printArrByName(arr, 5);
    for (int i = 0; i < 5; i++)
        free(arr[i].name);
    free(arr);
    return 0;
}