🔒 Locked

Merge Sort

Started by CottonCandyRandy Oct 24, 2012 at 6:56 PM 2 replies 2.3k views

Original Post

Oct 24, 2012 at 6:56 PM

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...

CottonCandyRandy

Oct 24, 2012 at 6:58 PM


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

rip-off

Oct 24, 2012 at 8:14 PM

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

Oct 24, 2012 at 8:15 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.