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

Question

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;
}

Eric Postpischil · Accepted Answer · 2019-04-02 09:57:29Z

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 Apr 2, 2019 at 9:57

Eric Postpischil

233k15 gold badges199 silver badges379 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mistguard Over a year ago

yes it work now ! thank you very much !! I was supposing that there was a problem with stack limit but I forgot this array, I should have seen it ^^' Thank you again !

Weather Vane Over a year ago

Eric you were first so +1. I was busy testing the modified code.

Weather Vane · Accepted Answer · 2019-04-02 10:03:49Z

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 Apr 2, 2019 at 10:03

Weather Vane

34.8k7 gold badges43 silver badges63 bronze badges

3 Comments

Mistguard Over a year ago

Thank you for your help ! I got it that there is something messy with the n being too large but I what is doing the 'puts()' function ?

Weather Vane Over a year ago

The puts is a cheap way of informing malloc failure, but should be something better.

chqrlie Over a year ago

Allocation malloc((fin+1) * sizeof *temp); in each recursive call is wasteful. For a set of 1 million elements, the memory required for the sort will be up to 80 MB instead of just 4 MB, or even 2 MB with a slightly more elaborate approach.

rcgldr · Accepted Answer · 2019-04-03 03:08:14Z

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 Apr 3, 2019 at 3:08

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related