• Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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 smile.png Please find the code below... Edited by cnewbie

Share this post


Link to post
Share on other sites
Advertisement

#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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement