• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Merge Sort

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1Prof G  Members

Posted 24 October 2012 - 12: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...

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

Done > Perfect

### #2Prof G  Members

Posted 24 October 2012 - 12: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[i]);

}



Done > Perfect

### #3rip-off  Moderators

Posted 24 October 2012 - 02: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?

### #4fastcall22  Moderators

Posted 24 October 2012 - 02: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.

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

zlib: eJzVVLsSAiEQ6/1qCwoK i7PxA/2S2zMOZljYB1TO ZG7OhUtiduH9egZQCJH9 KcJyo4Wq9t0/RXkKmjx+ cgU4FIMWHhKCU+o/Nx2R LEPgQWLtnfcErbiEl0u4 0UrMghhZewgYcptoEF42 YMj+Z1kg+bVvqxhyo17h nUf+h4b2W4bR4XO01TJ7 qFNzA7jjbxyL71Avh6Tv odnFk4hnxxAf4w6496Kd OgH7/RxC

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.