"free(): invalid next size (fast)" error when trying to free memory of array

Question

I am writing one of the merge sort variations. In my task I use two arrays: keys in arr array and values in brr array. Keys are integer numbers and values are strings. Merge function receives these two arrays, l, m and r as left, middle and right indexes.

void merge(int arr[], char** brr, int l, int m, int r)

I calculate the sizes of two new arrays, that I will need:

int size1 = m-l+1;
int size2 = r-m;

To merge arrays, I create two new arrays for keys and strings using malloc function:

int* left = malloc(size1*sizeof(int));
int* right = malloc(size2*sizeof(int));
char** lefts = malloc(size1*sizeof(char*));
char** rights = malloc(size2*sizeof(char*));

Then I copy values from the input arrays:

for(int i = 0; i < size1; i++){
    left[i] = arr[l+i];
    lefts[i] = brr[l+i];
}

And do sorting steps with new arrays.

i = j = 0;
k = l;
while(i < size1 && j < size2){
    if(left[i] < right[j]){
        brr[k] = lefts[i];
        arr[k] = left[i];
        i++;
    }else{
        brr[k] = rights[j];
        arr[k] = right[j];
        j++;
    }
    k++;
}

Then I add to brr arrays last items and after trying to free memory of rights array I get an error.

free(lefts);
lefts = NULL;
free(rights);
rights = NULL;

Note: there is no error when trying to free memory of lefts array, only rights. I tried to swap free(lefts) and free(rights), but result is the same.

Full function code:

void merge(int arr[], char** brr, int l, int m, int r){
    int size1 = m-l+1;
    int size2 = r-m;
    int* left = malloc(size1*sizeof(int));
    int* right = malloc(size2*sizeof(int));
    char** lefts = malloc(size1*sizeof(char*));
    char** rights = malloc(size2*sizeof(char*));

    for(int i = 0; i < size1; i++){
        left[i] = arr[l+i];
        lefts[i] = brr[l+i];
    }
    for(int i = 0; i < size2; i++){
        right[i] = arr[m+1+i];
        rights[i] = brr[m+1+i];
    }
    int i, j, k;
    i = j = 0;
    k = l;
    while(i < size1 && j < size2){
        if(left[i] < right[j]){
            brr[k] = lefts[i];
            arr[k] = left[i];
            i++;
        }else{
            brr[k] = rights[j];
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while(i < size1){
        brr[k] = lefts[i];
        arr[k] = left[i];
        k++;
        i++;
    }
    while(j < size2){
        brr[k] = rights[j];
        arr[k] = right[j];
        k++;
        j++;
    }
    free(left);
    left = NULL;
    free(right);
    right = NULL;
    free(lefts);
    lefts = NULL;
    free(rights);
    rights = NULL;
}

MergeSort function:

void mergeSort(int arr[], char** brr, int l, int r){
    if(l < r){
        int m = l+(r-l)/2;
        mergeSort(arr, brr, l, m);
        mergeSort(arr, brr, m+1, r);
        merge(arr, brr, l, m, r);
    }
}

Main:

int main(){
    const int maxStrings = 14;
    const int maxStringSize = 70;
    int n;

    scanf("%d", &n);
    getchar();

    int *Keys = malloc(n*sizeof(int));
    for(int i = 0; i < maxStrings; i++) Keys[i] = i;

    char **Strings = malloc(n*sizeof(char*));
    char *temp;
    for(int i = 0; i < n; i++){
        getStr(&temp, maxStringSize);
        Strings[i] = temp;
    }
    mergeSort(Keys, Strings, 0, n-1);
}

getStr:

void getStr(char **a, int n){
    *a = malloc(n*sizeof(char));
    char c;
    int i = 0;
    while( (c = getchar()) != '\n' && i < n-1){
        if(c == EOF){
            (*a)[i] = '\0';
            return;
        }
        (*a)[i++] = c;
    }
    (*a)[i] = '\0';
}

Answer 1

The error is typically a sign of overwriting some memory that doesn't belong to you. Typically you have destroyed the "mallocs book-keeping data" for the variable you are freeing.

So look for illegal memory writes. How about this code?

int *Keys = malloc(n*sizeof(int));
for(int i = 0; i < maxStrings; i++) Keys[i] = i;

You malloc only n elements but still you write maxStrings elements. So if n is less than maxStrings you have a write out side allocated memory.