Program crashes when given a big number
I'm trying to make a merge sort algorithm
in C. The problem is that it does not work for a big number of elements. If the array has 100000 elements it's OK but if it has 1e6 or 1e7 then it crashes. I thought that you cannot give such a big number of elements for an array but after I have read that this is not true, you should be able to give 1e7 elements. After that I thought that maybe int
range is to small but that's not the case, int
goes to 1e9. I don't really know what's the problem and why it doesn't work, so please help. Thanks in advance!
#include <stdio.h>
#include <stdlib.h>
int n;
void merge(int *, int, int);
void mergeSort(int *, int, int);
void bubbleSort(int *, int);
int main() {
// scanf("%d",&n);
n = 10000000;
int *a = (int *)malloc(n * sizeof(int));
if (a == NULL) {
printf("Nu sa putut aloca memorie.");
exit(0);
}
for (int i = 0; i < n; i++)
a[i] = rand() % 50;
mergeSort(a, 0, n  1);
//bubbleSort(a, n  1);
// for (int i = 0; i < n; i++) {
// printf("%d ", a[i]);
// }
free(a);
return 0;
}
void merge(int *a, int start, int sfarsit) {
int mij = (start + sfarsit) / 2;
int i = start;
int j = mij + 1;
int k = start;
int aux[10000000];
while (i <= mij && j <= sfarsit) {
if (a[i] < a[j])
aux[k++] = a[i++];
else
aux[k++] = a[j++];
}
while (i <= mij)
aux[k++] = a[i++];
while (j <= sfarsit)
aux[k++] = a[j++];
for (int i = start; i <= sfarsit; i++)
a[i] = aux[i];
}
void mergeSort(int *a, int start, int sfarsit) {
if (start >= sfarsit)
return ;
int mij = (start + sfarsit) / 2;
mergeSort(a, start, mij);
mergeSort(a, mij + 1, sfarsit);
merge(a, start, sfarsit);
}
2 answers

This:
int aux[10000000];
is problem. That will be to much for the stack to handle. Change to this:
int *aux = malloc(sizeof(*aux) * 10000000);
Of course, you need to use
free(aux)
in the end of the functionmerge
and also check if the allocation was successful.Also, you should of course allocate in relation to
sfarsit
but judging from your other code, it does not seem like I need to tell you that. 
Your program has this problem: the definition
int aux[10000000];
in themerge
function defines a temporary array with automatic storage (aka on the stack) which is: very large, potentially too large for your system, causing a stack overflow.
 not necessary large enough if the array to be sorted is larger than 10 million elements.
You should allocate this temporary array, either locally in
merge
or in a wrapper function that would callmergesort
with an extra argument.It is also unnecessary and quite error prone to make
n
a global variable.Here is a modified version:
#include <stdio.h> #include <stdlib.h> int mergeSort(int *a, int length); void bubbleSort(int *, int); int main() { int n; int *a; n = 10000000; //scanf("%d", &n); if ((a = malloc(sizeof(*a) * n)) == NULL) { printf("Nu sa putut aloca memorie."); return 1; } for (int i = 0; i < n; i++) a[i] = rand() % 50; mergeSort(a, n); //bubbleSort(a, n); for (int i = 1; i < n; i++) { if (a[i] < a[i  1]) { printf("mergeSort failed\n"); break; } } free(a); return 0; } void merge(int *a, int start, int mij, int sfarsit, int *aux) { int i = start; int j = mij + 1; int k = start; while (i <= mij && j <= sfarsit) { if (a[i] <= a[j]) aux[k++] = a[i++]; else aux[k++] = a[j++]; } while (i <= mij) aux[k++] = a[i++]; while (j <= sfarsit) aux[k++] = a[j++]; for (i = start; i <= sfarsit; i++) a[i] = aux[i]; } void mergeSortAux(int *a, int start, int sfarsit, int *aux) { if (start >= sfarsit) return; int mij = (start + sfarsit) / 2; mergeSortAux(a, start, mij, aux); mergeSortAux(a, mij + 1, sfarsit, aux); merge(a, start, mij, sfarsit, aux); } int mergeSort(int *a, int length) { if (length > 1) { int *aux = malloc(sizeof(*aux) * length); if (aux == NULL) return 1; mergeSortAux(a, 0, length  1, aux); free(aux); } return 0; }
Note that you can improve this code:
 using
size_t
instead ofint
for the array sizes and index variables  using the convention
start
included andstop
excluded, which avoids the+1
/1
adjustments.  by not copying the remaining values from the right slice as they are already in place in the original array.
Here is a modified version:
#include <stdio.h> #include <stdlib.h> int mergeSort(int *a, size_t length); int main(int argc, char *argv[]) { size_t n = 10000000; int *a; int res = 0; if (argc > 1) { n = strtoll(argv[1], NULL, 0); } if ((a = malloc(sizeof(*a) * n)) == NULL) { printf("Nu sa putut aloca memorie."); return 1; } for (size_t i = 0; i < n; i++) { a[i] = rand() % 50; } if (mergeSort(a, n)) { printf("mergeSort failed: allocation error\n"); res = 1; } else { for (size_t i = 1; i < n; i++) { if (a[i] < a[i  1]) { printf("mergeSort failed: out of order\n"); res = 1; break; } } } free(a); return res; } void merge(int *a, size_t start, size_t mid, size_t stop, int *aux) { size_t i = start; size_t j = mid; size_t k = start; while (i < mid && j < stop) { if (a[i] <= a[j]) aux[k++] = a[i++]; else aux[k++] = a[j++]; } while (i < mid) aux[k++] = a[i++]; for (i = start; i < k; i++) a[i] = aux[i]; } void mergeSortAux(int *a, size_t start, size_t stop, int *aux) { if (stop  start >= 2) { size_t mid = start + (stop  start) / 2; mergeSortAux(a, start, mid, aux); mergeSortAux(a, mid, stop, aux); merge(a, start, mid, stop, aux); } } int mergeSort(int *a, size_t length) { if (length > 1) { int *aux = malloc(sizeof(*aux) * length); if (aux == NULL) return 1; mergeSortAux(a, 0, length, aux); free(aux); } return 0; }