3 replies to this topic

[Prof G]

I'm not new to programming, but new to the C language. I'm using it as my vehicle for exploring different classic algorithms and I'm a bit stumped when it comes to this particular divide-and-conquer algorithm known as Merge Sort. I understand conceptually how it is supposed to work, but when actually implementing it in a programming language, my code below is causing my program to crash.

Any help or feedback would be appreciated! Oh and no, this isn't a homework assignment Please find the code below...

Edited by cnewbie, 24 October 2012 - 12:58 PM.

[Prof G]

#include <stdlib.h>

#include <stdio.h>

#include <time.h>



const int ARRAY_SIZE = 11;

void merge_sort(int a[], int l, int r);

void merge(int a[], int i, int j, int k, int size);

void print_array(int* a[]);

int main(){

    int a[] = {10,9,8,7,6,5,4,3,2,1,0};

    printf("AFTER SORT\n");

    clock_t begin, end;

    double time_spent;

    begin = clock();

    merge_sort(a,0,ARRAY_SIZE);

    end = clock();

    time_spent = (float)(end - begin)/ CLOCKS_PER_SEC;

    printf("TOOK: %f TO SORT", time_spent);

    getchar();

}

void merge_sort(int a[], int l, int r)

{

    int mid;

    if(r <= l)

	    return;

    mid = (r+l-1)/2;

    merge_sort(a, l, mid);

    merge_sort(a, mid+1, r);

    merge(a, l, mid, r, r-l+1);

}

void merge(int a[], int i, int j, int k, int size)

{

    int ipos = i;

    int jpos = j+1;

    int mpos = 0;

    int m[size];

    while(ipos <= j || jpos <= k){

	    if(ipos <= j && jpos <= k){

		    if(a[ipos] <= a[jpos]){

			    m[mpos] = a[ipos];

			    mpos++;

			    ipos++;

		    }else if(a[jpos] <= a[ipos]){

			    m[mpos] = a[jpos];

			    mpos++;

			    jpos++;

		    }

	    }else if(ipos > j){

		    while(jpos <= k){

			    m[mpos] = a[jpos];

			    mpos++;

			    jpos++;

		    }

	    }else if(jpos > k){

		    while(ipos < j){

			    m[mpos] = a[ipos];

			    mpos++;

			    ipos++;

		    }

	    }

    }

    return m;

}

void print_array(int* a[]){

    int i = 0;

    for(i = 0; i < ARRAY_SIZE; i++)

	    printf("%d: %d\n", i+1, a[i]);

}

[rip-off]

Your crash is almost certainly caused by out-of-bounds access. One way to start is using a debugger, another is to add assertions.

I find it hard to follow your code because of the poor variable names. Are you sure you need all those variables and parameters for the "merge" function?

[fastcall22]

You cannot return m in merge because merge is defined not to return a value and m is an array on the stack. As soon as merge returns, the memory that contained the array for m is destroyed/trashed/undefined/etc. You will either need to use dynamic memory allocation (malloc and free) to create and return the array m, or use the in-place flavor of merge sort.

Also, watch your ipos and jpos carefully, as a[jpos] is an invalid element when jpos == k == ARRAY_SIZE.

Edited by fastcall22, 24 October 2012 - 02:17 PM.