# 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 s-a 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;

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

This:

``````int aux;
``````

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 function `merge` 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;` in the `merge` 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 call `mergesort` 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 s-a 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 of `int` for the array sizes and index variables
• using the convention `start` included and `stop` 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, NULL, 0);
}
if ((a = malloc(sizeof(*a) * n)) == NULL) {
printf("Nu s-a 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;
}
``````