Program crashes when array size is one million

Question

Possible Duplicate:
Big array gives segmentation error in C

i'm trying to compare merge sort and quick sort with different input sizes like 10.000, 100.000, and 1.000.000. However, when i give one million input size program is crashing and i don't know why ?.On the other hand, array is filled with reading from a file which contains numbers and here is my simple merge sort.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define SIZE 1000000

void Merge(int * , int , int , int );
void MergeSort(int *array, int left, int right);

int main(){

    struct timeval tv; 
    struct timezone tz; 
    struct tm *tm; 
    long start,stop;

    long i,num;
    int array[SIZE];

    FILE* fptr;

    gettimeofday(&tv, &tz); 
    tm = localtime(&tv.tv_sec); 
    printf("TIMESTAMP-START\t %d:%02d:%02d:%d (~%d ms)\n", tm->tm_hour, 
    tm->tm_min, tm->tm_sec, tv.tv_usec, 
    tm->tm_hour * 3600 * 1000 + tm->tm_min * 60 * 1000 + 
    tm->tm_sec * 1000 + tv.tv_usec / 1000);

    start = tm->tm_hour * 3600 * 1000 + tm->tm_min * 60 * 1000 + tm->tm_sec * 1000 + tv.tv_usec / 1000;

    fptr = fopen ("onemillion.txt","r");

    for(i=0; i<SIZE-1; i++){

        fscanf(fptr,"%d",&num);
        array[i]=num;
    }

    MergeSort(array,0,SIZE-1);

    /*for(i = 0;i < SIZE;i++)
        {
                printf("%d \n",array[i]);
        }*/

    gettimeofday(&tv, &tz); 
    tm = localtime(&tv.tv_sec); 
    stop = tm->tm_hour * 3600 * 1000 + tm->tm_min * 60 * 1000 + 
    tm->tm_sec * 1000 + tv.tv_usec / 1000; 
    printf("TIMESTAMP-END\t %d:%02d:%02d:%d (~%d ms) \n", tm->tm_hour, 
    tm->tm_min, tm->tm_sec, tv.tv_usec, 
    tm->tm_hour * 3600 * 1000 + tm->tm_min * 60 * 1000 + 
    tm->tm_sec * 1000 + tv.tv_usec / 1000); 

    printf("ELAPSED\t %d ms\n", stop - start);

    return 0;

}

void MergeSort(int *array, int left, int right)
{
        int mid = (left+right)/2;
        /* We have to sort only when left<right because when left=right it is anyhow sorted*/
        if(left<right)
        {
                /* Sort the left part */
                MergeSort(array,left,mid);
                /* Sort the right part */
                MergeSort(array,mid+1,right);
                /* Merge the two sorted parts */
                Merge(array,left,mid,right);
        }
}

void Merge(int *array, int left, int mid, int right)
{
        /*We need a Temporary array to store the new sorted part*/
        int tempArray[right-left+1];
        int pos=0,lpos = left,rpos = mid + 1;
        while(lpos <= mid && rpos <= right)
        {
                if(array[lpos] < array[rpos])
                {
                        tempArray[pos++] = array[lpos++];
                }
                else
                {
                        tempArray[pos++] = array[rpos++];
                }
        }
        while(lpos <= mid)  tempArray[pos++] = array[lpos++];
        while(rpos <= right)tempArray[pos++] = array[rpos++];
        int iter;
        /* Copy back the sorted array to the original array */
        for(iter = 0;iter < pos; iter++)
        {
                array[iter+left] = tempArray[iter];
        }
        return;
}

when i try with one thousand, ten thousand and one hundred thousand there is no problem. As i said i struggle with one million input size. I'm not sure but i guess it is about using an array ?. I will be glad if you can help and thanks anyway.

score 4 · Accepted Answer · answered Dec 16 '12 at 13:14

4

You are getting an stack overflow. There is not enough stack memory to accommodate your request resulting in run-time exception.

Try allocating the array dynamically using malloc.

answered Dec 16 '12 at 13:14

Alok Save

202,538
53
430
533

score 2 · Answer 2 · answered Dec 16 '12 at 13:16

2

C is very strict and cannot decide where to put the array, like other languages. It allways puts such an array on the stack, which is small. Use dynamic allocation.

answered Dec 16 '12 at 13:16

Vladimir F Героям слава

57,977
4
76
119

3

Did someone just say C is *very* *strict*? – Dec 16 '12 at 13:20
It depends on the sense of the word *strict*. Of course you can do what you want with the pointers. In the sense I used it means not the freedom of the programmer, but freedom of the compiler. It simply has allocate the array via automatic storage. In other languages, the compiler can decide. – Vladimir F Героям слава Dec 16 '12 at 13:29

Program crashes when array size is one million

2 Answers2

Linked

Related