Segmentation fault in quick and merge sorts

[balgarath]

okay I am getting segmentation fault whenever I pass more than 300000 ints or so to be sorted....the code works fine for less than this with mergesort

quicksort is sorting 100000 fine if they are in random order, but seg faulting if I sort a bigger number, or if the numbers are in reverse order

Any help would be appreciated...

MERGESORT

mergesort(int *a, int size)        //a is pointer to the array, size is # of elements
{

    int b[(size/2)];
    int c[(size-(size/2))];
    int *bp;
    int *cp;
    int x;
    int y;
    bp = b;
    cp = c;

    if(size > 1)
    {

        for(x = 0; x < (size/2); x++)
        {
            b[x] = *(a + x);
            
        }
        for(y = 0; y < (size - (size/2)); y++)
        {
            c[y] = *(a + x);
            x++;
        }

        mergesort(bp, (size/2));
        mergesort(cp, (size - (size/2)));
        merge(a, bp, cp, size);
    }
}

merge(int *a, int *b, int *c, int size)
{
    int i = 0, j = 0, k = 0;
    while(i < (size/2) && j < (size - (size/2)))
    {
        if(*(b + i) < *(c + j))
        {
            *(a + k) = *(b + i);
            i++;
        }
        else
        {
            *(a + k) = *(c + j);
            j++;
        }
        k++;
    }
    if(i == (size/2))
    {
        while(j < (size - (size/2)))
        {
            *(a + k) = *(c + j);
            k++;
            j++;
        }
    }
    else
    {
        while(i < (size/2))
        {
            *(a + k) = *(b + i);
            k++;
            i++;
        }
    }
}

QUICKSORT

quicksort(int *a, int size)
{
    q_sort(a, 0, size - 1);
}

q_sort(int *a, int l, int r)
{
    int s;
    //printf("\n%d - size", (r - l));
    if(l < r)
    {
        s = partition(a, l, r);
        q_sort (a, l, s - 1);
        q_sort(a, s + 1, r);
    }
}

int partition(int *a, int l, int r)
{
    int i, j, p;
    p = *(a + l);
    i = l;
    j = r + 1;
    while(1 < 2)
    {
        do ++i;
        while(*(a + i) <= p && i <= r);
        do --j;
        while (*(a + j) > p && j >=l);
        if(i >= j) break;
        swap(a, i, j);
    }
    swap(a, l, j);
    return j;
}

swap(int *a, int b, int c)
{
    int temp = *(a + b);
    *(a + b) = *(a + c);
    *(a + c) = temp;
}

And this is what I'm using to test with

#include <stdio.h> 
#include "sorting.c" 
#include <time.h>
main() 
{
    int size = 100000, a[size], *ap, x;
    ap = a;
    time_t t0, t1;
    clock_t c0, c1;

    for(x = 0; x < size; x++)        
    {
        //a[x] = size - x;        //set array in reverse order
        a[x] = random()%size;    //set array in random order
    }
    t0 = time(NULL);
    c0 = clock();
    printf("\nMergesorting\n");
    mergesort(ap, size);
    t1 = time(NULL);
    c1 = clock();
    /*for(x = 0; x < size; x++)    //print contents of array
    {
        printf("\n%d", a[x]);
    }*/    
    printf("\nMergesort(%d items)\nTime Difference: %f\tClock Cycle Difference:  %f\n",size, (float) (t1-t0),(float) (c1-c0));    
    size = 100000;
    for(x = 0; x < size; x++)        
    {
        a[x] = size - x;        //set array in reverse order
        //a[x] = random()%size;    //set array in random order
    }
    
    t0 = time(NULL);
    c0 = clock();
    quicksort(ap, size);
    t1 = time(NULL);
    c1 = clock();
    /*for(x = 0; x < size; x++)        //print contents of array
    {
        printf("\n -%d", a[x]);
    }*/    
    
    printf("\nQuicksort(%d items)\nTime Difference: %f\tClock Cycle Difference:  %f\n",size, (float) (t1-t0),(float) (c1-c0));    
}

Thanks for the help!

[Ancient Dragon]

I'm not supprised -- it is probably stack overflow problem with all those recursive calls and putting all those huge arrays on the stack. Try putting that array in global memory, outside any function and maybe use a non-recursive algorithm.