Mergesort of dynamic array of doubles using malloc, memory prob

Question

Hey everyone so my MergeSort algorithm isn't perfect, it's actually the same one that was posted here in a similar question, but that's not even the real problem. Basically the user inputs an array size, and lower & upper bounds on a range of values to be put into an array of doubles to be mergeSorted.

I can print out the array just fine but after MergeSort it returns whack negative values that I assume are addresses.

I know this has something to do with memory but I have no idea why it's messing up because I believe I allocated memory and cleared it correctly. Here is my code, any insight will be much appreciated especially before 12:00 tonight ;).

Here is main.c, mergesort.c, and mergesort.h. I am also using a makefile but I don't think that is necessary to share.

Main.c:

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

int lower = 0;
int upper = 0;
int n = 0;

int main(int argc,char* argv[]) {

    int i = 0; // loop values
    int j = 0;
    int r = 0; // random number

    /*int n = 0; // size of array
    int lower = 0; // lower bound on values in array
    int upper = 0; // upper ...*/

    double *t; //array of doubles

    printf("Size of array?\n");
    scanf("%d", &n);

    printf("Lower Bound?\n");
    scanf("%d", &lower);
    //globLower = lower;

    printf("Upper Bound?\n");
    scanf("%d", &upper);
    //globUpper = upper;

    t = malloc(n * sizeof *t); // allocates n slots of memory


    printf("Unsorted Array:\n");

    for(i=0; i<n; i++) {
        r = lower + arc4random() % (upper - lower);

        //printf("%d\n", r);
        t[i] = r;   // fills array with random values in range
        printf("%g\n", t[i]);
    }


    printf("Before Merge Sort\n");

    mergeSort(t,n); // This is supposed to sort the array...

    printf("After Merge Sort\n");

    i = 0; //reset
        // printf("%g\n", t[0]);
        printf("%g\n", t[1]);
        printf("%g\n", t[2]);



    free(t);   // Need to free the memory allocated since is stored in the heap
    return 0; 
 }    

mergesort.c:

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

void mergeSort(double* t, int n) {
    printf("Size: %d\n", n);
    printf("Lower: %d\n", lower);     // tests
    printf("Upper: %d\n", upper);
    printf("t[2]: %g\n", t[2]);
    int beg = 0;
    int end = n-1;
    mergeSortHelp(t, beg, end);
}

void mergeSortHelp(double* t, int beg, int end) {
    int mid = (end + beg) / 2;

    if(beg < end) {
        mergeSortHelp(t, beg, mid);
        mergeSortHelp(t, mid+1, end);
        merge(t, beg, mid, end);
    }
}

void merge(double* t, int beg, int mid, int end) {
    int sizeLeft = mid - beg + 1;
    int sizeRight = end - mid;
    double *left = malloc((sizeLeft)*sizeof(double));
    double *right = malloc((sizeRight)*sizeof(double));
    int i,j,k;

for(i = 0; i < sizeLeft; i++) {
    left[i] = t[beg+i];
}
for(j = 0; j < sizeRight; j++) {
    right[i] = t[beg+j];
}

i = 0;
j = 0;

for(k = beg; k <= end; k++) {
    t[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
}

free(left);
free(right);

return;
}

and the header mergesort.h

extern int lower;   
extern int upper;
extern int n;

Thanks!

Answer 1

It looks like you may have two bugs here:

for(j = 0; j < sizeRight; j++) {
    right[i] = t[beg+j];

This should probably be:

for(j = 0; j < sizeRight; j++) {
    right[j] = t[med+j];
         ^^^     ^^^