# Merge Sort

This topic is 1917 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
 #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); } 

##### Share on other sites
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?

##### Share on other sites
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