Merge-sort issue!

**Kadmany** · 05-28-2011

yo yo sup?
so I get this Merge-Sort to be implemented in c,look:

**Please notes this:1-The arrays are not sorted and still I got to merge them.

2-Running time must be of order O(n*log(n))
3-The following code works but I get Runtime Error,so mainly I need your help to find out where the Runtime Error occurs!
4-the two arrays of the same size

Code:

int merge_sort(int arr1[], int n)
{
int len;
int*temp_array,*base;temp_array=(int*)malloc(sizeof(int)*n);
if(temp_array==NULL){
    printf("Dynamic Allocation Error in merge_sort");
    return FAILURE;
    }
    for(len=1;len<n;len*=2){
        for(base=arr1;base<arr1+n;base+=2*len){
              merge(base,len,base+len,len,temp_array);
              memcpy(base,temp_array,1*len*sizeof(int));
            }
        }
    free(temp_array);
    return SUCCESS;
}
void merge(int a[],int na,int b[],int nb,int c[])
{
 int ia,ib,ic;
 for(ia=ib=ic=0;(ia<na) && (ib<nb);ic++){
    if(a[ia]<b[ib]){
        c[ic]=a[ia];
        ia++;
        }
        else{
            c[ic]=b[ib];
            ib++;
            }
    }
    for(;ia<na;ia++,ic++)c[ic]=a[ia];
    for(;ib<nb;ib++,ic++)c[ic]=b[ib];
}

as u see i implemented merge too,

My problem is that this code works for arrays of length of power to 2,I need it to work for any length of an array,(in the first 'for' loop)

what u think?

Thanks!

**Kadmany** · 05-28-2011

man I am trying my best but still unable to to make this work for any length of an array,plz help

!

**cas** · 05-28-2011

I suggest rereading a description of merge sort. Make sure you understand how it works before you try implementing it.

The entire point of merge sort is that it's a divide and conquer algorithm--it's recursive. That means that merge_sort() should be calling itself.

**~~CommonTater~~** · 05-28-2011

Originally Posted by Kadmany

man I am trying my best but still unable to to make this work for any length of an array,plz help

!

In addition to the advice from Cas --whom I agree with-- you probably should turn off the computer and work the problem with pencil and paper until you understand it. As others here correctly advise: if you can't verbalize the solution, you don't actually understand the problem.

Once you reach that point, tapping out the code should be rather easy.

Try this on for size... (No need to post it here, this is for yourself)...
In words --not code-- write a step by step description of what your merge sort has to do.

**Kadmany** · 05-28-2011

Originally Posted by CommonTater

In addition to the advice from Cas --whom I agree with-- you probably should turn off the computer and work the problem with pencil and paper until you understand it. As others here correctly advise: if you can't verbalize the solution, you don't actually understand the problem.

Once you reach that point, tapping out the code should be rather easy.

Try this on for size... (No need to post it here, this is for yourself)...
In words --not code-- write a step by step description of what your merge sort has to do.

Hey everyone,thanks for help,but I must mentiona few things,this code was taken from a lecture,it was designed for array which their length is of the power 2,it should work fine the only thing is must be modified if the loop for and small thing,If you know a better solution to find two common numbers of the two array of time O(n*log(n)) then I will be happy to know that!

**cas** · 05-28-2011

You probably should have explained the requirements in your first post; it only said that the problem is that this works for powers of 2 (which I hardly see as a problem, if that's the goal of the sort...)

Anyway, I see now how this approach is supposed to work, knowing that it's for power-of-two sized arrays only. It's a rather interesting way of converting a recursive algorithm to an iterative one. Yet the only substantive issue you've raised, that I can see, is that you get a runtime error. In such cases, your first stop should be a debugger. I recommend Valgrind if it's available for your platform; otherwise, use whatever native debugger you have (gdb, xdb, etc).

However, I still recommend learning how merge sort works. Once you understand merge sort, you should be able to see how it can be optimized for a power-of-two sized array. Then you'll understand what this algorithm is supposed to be doing.

**Kadmany** · 05-28-2011

Originally Posted by cas

You probably should have explained the requirements in your first post; it only said that the problem is that this works for powers of 2 (which I hardly see as a problem, if that's the goal of the sort...)

Anyway, I see now how this approach is supposed to work, knowing that it's for power-of-two sized arrays only. It's a rather interesting way of converting a recursive algorithm to an iterative one. Yet the only substantive issue you've raised, that I can see, is that you get a runtime error. In such cases, your first stop should be a debugger. I recommend Valgrind if it's available for your platform; otherwise, use whatever native debugger you have (gdb, xdb, etc).

However, I still recommend learning how merge sort works. Once you understand merge sort, you should be able to see how it can be optimized for a power-of-two sized array. Then you'll understand what this algorithm is supposed to be doing.

Hey man,I think I better fix my english :P,No,I ment that the algorithm is designed for power-of-two arrays only,I need that for any poer-of-number hehe

**iMalc** · 05-28-2011

Originally Posted by Kadmany

Hey everyone,thanks for help,but I must mentiona few things,this code was taken from a lecture,it was designed for array which their length is of the power 2,it should work fine the only thing is must be modified if the loop for and small thing,If you know a better solution to find two common numbers of the two array of time O(n*log(n)) then I will be happy to know that!

It is indeed not particularly hard to make that breadth-first merge sort code work for non-powers of two. It's simply a matter of passing the right arguments into merge to not overflow the array bounds. Right now you're passing in "len" and "len" as the lengths of the subarrays, Instead of pasing "len" for the length of the second subarray to merge, you pay attention to when "base+len (where the second half starts) + len" would exceed n, and pass in a different value for the second array length that does not exceed n.

**Kadmany** · 05-28-2011

Originally Posted by iMalc

It is indeed not particularly hard to make that breadth-first merge sort code work for non-powers of two. It's simply a matter of passing the right arguments into merge to not overflow the array bounds. Right now you're passing in "len" and "len" as the lengths of the subarrays, Instead of pasing "len" for the length of the second subarray to merge, you pay attention to when "base+len (where the second half starts) + len" would exceed n, and pass in a different value for the second array length that does not exceed n.

Hey IMalc,I think I understand what you sayin,the only thing is what should I change the base + len to? Could you please write me the same two for loops with the right argument passing?

Thank you very much ahead!

**iMalc** · 05-29-2011

I don't think you actually need to change base+len. If base+len is not less than n then don't call merge at all. If only the first of the two subarray's fits below n, then there is nothing to merge it with.

Looking at my own implementation of this that I wrote ages ago, there is only two if-statements added, at least in terms of the difference to cyclomatic complexity. One is what I mentioned in my other post and one is what I mentioned in this post.

**Kadmany** · 05-29-2011

Originally Posted by iMalc

I don't think you actually need to change base+len. If base+len is not less than n then don't call merge at all. If only the first of the two subarray's fits below n, then there is nothing to merge it with.

Looking at my own implementation of this that I wrote ages ago, there is only two if-statements added, at least in terms of the difference to cyclomatic complexity. One is what I mentioned in my other post and one is what I mentioned in this post.

Hey man thanks again,I gotta say,i have already mentioned that I know there is an error in for loop plus I gotta improve it,I am just unable to geuss whaat these conditions!!
Couldnt you please just post them or send me a link to your written code? I am very tight in time And I WOULD REALLY APPRECIATE IT IF YOU HELP.

**Kadmany** · 05-30-2011

Guys plz whats the modifications must be done?

**cas** · 05-30-2011

I am just unable to geuss whaat these conditions!!

There's the crux of your issue. You're unwilling to learn how merge sort works, instead trying to guess, and when that fails, get others to do your work for you.

Go read about merge sort. Take a pencil and paper and do a merge sort, by hand, of a small list. Start with a power of 2 (try 8 elements) and figure out how your original code works (or is supposed to work). Once you understand that, it'll be easier to figure out how to sort any sized list with an iterative approach.

You're probably not going to get somebody to do your homework for you, so I'd recommend not begging for it.

**Kadmany** · 05-30-2011

Originally Posted by cas

There's the crux of your issue. You're unwilling to learn how merge sort works, instead trying to guess, and when that fails, get others to do your work for you.

Go read about merge sort. Take a pencil and paper and do a merge sort, by hand, of a small list. Start with a power of 2 (try 8 elements) and figure out how your original code works (or is supposed to work). Once you understand that, it'll be easier to figure out how to sort any sized list with an iterative approach.

You're probably not going to get somebody to do your homework for you, so I'd recommend not begging for it.

Its not to do my homework,here is what I know about merge-sort:
You get an array with random values in cells,You divide the array into two,then each part divided you divide again into two you keep doin that tell you get single elements,then you merge those with the other element which both of them splitted,you do that again with the other part from where these two part splitted you keep doing that tell you get the array sorted,

I am just unable to figure out a way to modify the code even though I understand that basically if the length of the array isnt of power two is to to try to split it into two parts where on of them is of power two,,,,

In addition,DUE to your kindness and very very supportive approach I have been trying to expand the array in case its length is not of power two:

Code:

  int i,closest_length_of_power_two,max;
  int *temp_array;

 if(!is_power_of_two(n)){
       closest_length_of_power_two=get_closest_length_of_power_two(n);
       max=find_max_in_array(arr2,n);
       temp_array=creat_new_array(closest_length_of_power_two);
       if(temp_array==NULL){
           printf("Dynamic Allocation Error in creat_new_array");
           return -1;
         }
       for(i=0;i<closest_length_of_power_two;i++){
             if(i<n){
                *(temp_array+i)=arr2[i];
               }
             if(i>=n){
                *(temp_array+i)=max+1;
               }
            }
        if(merge_sort(temp_array,closest_length_of_power_two)==1){
             for(i=0;i<closest_length_of_power_two;i++){
                  if(binary_search(temp_array,n,arr1[i])==1){
                      free(temp_array);
                      return 1;
                    }
                 }
           }
       }

and:

Code:

int* creat_new_array(int closest_length_of_power_two)
{
   int *temp_array;
   temp_array=(int*)malloc(sizeof(int)*(closest_length_of_power_two));

   return temp_array;
}

Notes:fucntion get_closest_length_of_power_two gets the smallest biggest power of two to the given array size,

Now I am still getting Runtime Error! why's that?

**Kadmany** · 05-31-2011

Guys,no any ideas?

Thread: Merge-sort issue!

Thread Tools

Search Thread

Display

Merge-sort issue!

Guys no one wants to helppppppp?????? :((((

Similar Threads

Merge sort fails to sort

Quick Sort or Merge Sort???

Merge Sort Help

Quick sort VS Merge Sort

merge sort and selection sort and time spent on both