How can I find why my merge sorting algorithm crash when sorting an array of 1 million element?

1

I'm a French student and trying to calculate the execution time of the Merge Sort algorithm for different size of array. I also want to write the different execution time in a .csv file. But when my program tries to sort an array with 1 million elements the process returns -1073741571 (0xC00000FD) in Code::Blocks. So if you could point me to a way to find a solution I would be very grateful!

Here is my code:

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

void genTab(int *tab, int n) {
    int i;
    for (i = 0; i < n; i++) {
        tab[i] = rand() % 100;  
    }
}

void fusion(int *tab, int deb, int mid, int fin) {
    int i = deb;
    int j = mid + 1;
    int k = deb;
    int temp[fin + 1];
    while ((i <= mid) && (j <= fin)) {
        if (tab[i] <= tab[j]) {
            temp[k] = tab[i];
            i++;
        } else {
            temp[k] = tab[j];
            j++;
        }
        k++;
    }
    while (i <= mid) {
        temp[k] = tab[i];
        i++;
        k++;
    }
    while (j <= fin) {
       temp[k] = tab[j];
       k++;
       j++;
    }

    for (i = deb; i <= fin; i++) {
        tab[i] = temp[i];
    }
}

void triFusion(int *tab, int i, int j) {
    if (i < j) {
        triFusion(tab, i, (int)((i + j) / 2));
        triFusion(tab, (int)((i + j) / 2 + 1), j);
        fusion(tab, i, (int)((i + j) / 2), j);
    }
}

void reset(int *tab1, int *tab2, int n) {
    for (int i = 0; i < n; i++) {       
        tab2[i] = tab1[i];
    }
}

int main() {
    srand(time(NULL));
    clock_t start, end;  

    int nbrTest[15] = {
        1000, 5000, 10000, 50000, 80000, 100000, 120000, 140000,
        150000, 180000, 200000, 250000, 300000, 450000, 1000000
    }; 
    FILE *fp;

    char *tpsExecution = "exeTime.csv";

    fp = fopen(tpsExecution, "w");

    fprintf(fp, "Array Size; Merge Time"); 

    for (int i = 0; i < 15; i++) {     
        int n = nbrTest[i];
        printf("Calculating time for an array of %d \n", n);
        int *tab = malloc(sizeof(int) * n);
        genTab(tab, n);      

        int *copie = malloc(sizeof(int) * n);
        reset(tab, copie, n);

        start = clock();
        triFusion(tab, 0, n - 1);
        end = clock();
        float tpsFusion = (float)(end - start) / CLOCKS_PER_SEC;

        reset(tab, copie, n);

        printf("writing in the file\n");
        fprintf(fp, "\n%d;%f", n, tpsFusion);    
        free(tab);
        free(copie);
    }
    fclose(fp);

    return 0;
}

c
arrays
crash
time-complexity
mergesort
asked on Stack Overflow Apr 2, 2019 by Mistguard • edited Apr 6, 2019 by chqrlie

3 Answers

2

int temp[fin+1]; may exceed the space limit for the stack. You should allocate it with malloc instead, and free it with free.

If you want to exclude malloc and free from the timed code, the allocation could be performed outside the timed code and passed in as work space.

answered on Stack Overflow Apr 2, 2019 by Eric Postpischil
1

(Note: posted after the answer from @Eric Postpischil).

The function

void fusion(int * tab, int deb, int mid, int fin)

Has the line

int temp[fin+1];

and the value of fin comes through another function from the number of elements n to be sorted

triFusion(tab, 0, n-1);

and as an automatic variable, breaks the stack when n is large.

I suggest replacing the line with

int *temp = malloc((fin+1) * sizeof *temp);
if(temp == NULL) {
    puts("malloc");
    exit(1);
}

// ...

free(temp);
answered on Stack Overflow Apr 2, 2019 by Weather Vane
1

fusion() is always allocating the full size of the array for temp, even when only a small fraction of temp is being used. You could change this to:

int k = 0;
...
int temp[fin+1-deb];
...
tab[i]=temp[i-deb];

still this will exceed stack space if n is large. So as suggested in the other answers:

int k = 0;
...
int *temp = malloc((fin+1-deb)*sizeof(int));
...
tab[i]=temp[i-deb];
...
free(temp)

or better still, do a one time allocation of a second array in main or in a "helper" function, the include a pointer to the second array in the merge sort functions.

answered on Stack Overflow Apr 3, 2019 by rcgldr

User contributions licensed under CC BY-SA 3.0