merge sort

I have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array, its size, and an help array(i.e mergesort(int [] array, int size, int[] temp] . I have to use only the temp array for the sorting,
and a merge function that takes 5 arguments - left array and its size, right array and its size, and final array

I think I know how to write the merge function but how do I write the recursive mergesort function?

Be more specific on what your problem, post some snaps of your code. Nobody is going to do your homework here.

Post your code, and tell us where you are stuck.

ssharish

http://en.wikipedia.org/wiki/Mergesort

Shows the basic Mergesort in action on integers, on the right hand side of the page. Note how, as long as the sub array has more than one element in it, you (recursively) divide that sub array, one more time.

Only when the sub array's are all the way down to one element, does the ordering of those elements take place, through merging.

I'm sure you can find some code on the net, but I urge you to study it enough to really understand what is going on here. Sorting is a part (sometimes a huge part), of most programs, and Mergesort is one of the best algorithms for sorting.

I'd like to note that the researchers who discovered these advanced algorithms, are/were, simply brilliant. You could do a lot worse than studying their approach to solving the problem of sorting.

this is my mergeSort function
I know that it suppose to be shorter, but I'm having troubles to do it with only 1 temp array

Code:

---


void mergeSort( int *Array, int Array_Size, int *temp )
{
        int  i, j, tmp, leftArr[100] = {0}, rightArr[100] = {0}, rightSize,leftSize,temp_Size;
       

        if (Array_Size < 2)
                return;
       

        leftSize = Array_Size/2;
        rightSize =  Array_Size - leftSize;

        temp_Size = leftSize;
       
        for( i = 0; i < leftSize; i++ )
                leftArr[i] = Array[i];

       
        for( i = 0; i < temp_Size; i++ )
        {
                temp[i] = Array[i];
        }

        mergeSort( leftArr, leftSize, temp );

        for( i = 0; i < temp_Size; i++ )          ///bubble sort
        {
                for( j = 0; j < temp_Size-1; j++ )
                {
                        if( temp[j] > temp[j+1] )
                        {
                                tmp = temp[j];
                                temp[j] = temp[j+1];
                                temp[j+1] = tmp;
                        }
                }
        }
       

        for( i = 0; i < temp_Size; i++ )
        {
                leftArr[i] = temp[i];
        }

        temp_Size = rightSize;
       
        for( i = 0; i < temp_Size; i++ )
        {
                temp[i] = Array[leftSize+i];
        }

        for( i = 0; i < temp_Size; i++ )    ///bubble sort
        {
                for( j = 0; j < temp_Size; j++ )
                {
                        if( temp[j] > temp[j+1] )
                        {
                                tmp = temp[j];
                                temp[j] = temp[j+1];
                                temp[j+1] = tmp;
                        }
                }
        }
               
        for( i = 0; i < temp_Size; i++ )
                rightArr[i] = temp[i];
       
        merge( leftArr, leftSize, rightArr, rightSize, Array );
}

---

Let me study your code a bit here.

Note that you bubblesort is incorrect. the i variable should start at 0 and stop at the NEXT to the highest array element, while j should start at i + 1, and stop at the highest array element. (or conversely, j should start at the highest array element and decrement down to j + 1.

OK, here's something that's close to what you're trying to do, I believe:

Code:

---

void seq_sort(int *array, int n, int *outarray)
{
    int i,j;
    int temp;
    for (i=0; i<n; i++) outarray[i] = array[i];
 
    for (i=0; i<n-1; i++)
      for (j=i+1; j<n; j++)
          if (outarray[i] > outarray[j]) {  /*swap:*/
            temp = outarray[i];
            outarray[i] = outarray[j];
            outarray[j] = temp;
        } /* end of if */
}

---

the problem with your code is that it's not recursive.
thats my problem, of course I can do merge sort that is not recursive or recursive with 2 temp array. but with 1, i'm a having a little problem

Quote:

---

Originally Posted by moooon

the problem with your code is that it's not recursive.
thats my problem, of course I can do merge sort that is not recursive or recursive with 2 temp array. but with 1, i'm a having a little problem

---

It WILL be recursive, though. I wasn't used to seeing Mergesort with the sort being done in ONE array only. I don't honestly see the point of bubblesorting the array. Why not MERGE it, in sorted order? Maybe I'm arguing semantics here, since the end result is the same. I always merged for mergesort though, never heard of bubblesorting it, actually.

So the above function is for sorting, using the 2 arrays and the size.

Now the mergesort function is usually seen as something like this:

Code:

---

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}

---

And this is a lot like Quicksort or Binary Search. You divide the work up into roughly two equal halves, work them out, and then continue picking new midpoints, as needed.

as I was saying before I MUST use only one array...
with two arrays I get it, with one not so much :(
and I dont have low and high in my function...
the teacher insist upon using only one array for all the sorting
do you have any idea on how to do it?

Quote:

---

Originally Posted by moooon

as I was saying before I MUST use only one array...
with two arrays I get it, with one not so much :(
and I dont have low and high in my function...
the teacher insist upon using only one array for all the sorting
do you have any idea on how to do it?

---

Yes, I told you:

Quote:

---

I have to use a function mergesort that takes 3 arguments - an array, its size, and an help array(i.e mergesort(int [] array, int size, int[] temp] . I have to use only the temp array for the sorting,

---

You'll use the temp array for sorting, ONLY. You'll use bubblesort on that temp array. Replace "outarray" with temp[] in the bubblesort post, above. Rename the int variable "temp" to something like "temp_int", so there's no confusion.

One idea is this:
1. Copy half the elements of the array into the helper array.
2. Perform mergesort on the helper array.
3. Copy back the elements of the helper array into the array.
4. Copy the other half of the elements of the array into the helper array.
5. Perform mergesort on the helper array.
6. Copy back the elements of the helper array into the array.
7. Merge the two halves of the array.
The array is sorted.

You do not need to use bubblesort, though if you want to it would be better to turn it into another function so as not to clutter your mergesort implementation.

adak, i changed my code as u said, but still something is not working right

Code:

---

void mergeSort( int *Array, int n, int *temp )
{
        int  leftArr[100] = {0}, rightArr[100] = {0}, rightSize,leftSize,temp_Size;
        int i,j,temp_int;
       
       

        if (n < 2)
                return;

        for (i=0; i<n; i++) temp[i] = Array[i];

        for (i=0; i<n-1; i++)
                for (j=i+1; j<n; j++)
                        if (temp[i] > temp[j]) {  /*swap:*/
                                temp_int = temp[i];
                                temp[i] = temp[j];
                                temp[j] = temp_int;
                        } /* end of if */
       

        leftSize = n/2;
        rightSize =  n - leftSize;

        temp_Size = leftSize;
       
        for( i = 0; i < leftSize; i++ )
                leftArr[i] = Array[i];

       
        for( i = 0; i < temp_Size; i++ )
        {
                temp[i] = Array[i];
        }

        mergeSort( leftArr, leftSize, temp );

        for( i = 0; i < temp_Size; i++ )
        {
                leftArr[i] = temp[i];
        }

        temp_Size = rightSize;
       
        for( i = 0; i < temp_Size; i++ )
        {
                temp[i] = Array[leftSize+i];
        }

        for (i=0; i<n-1; i++)
                for (j=i+1; j<n; j++)
                        if (temp[i] > temp[j]) {  /*swap:*/
                                temp_int = temp[i];
                                temp[i] = temp[j];
                                temp[j] = temp_int;
                        } /* end of if */
               
        for( i = 0; i < temp_Size; i++ )
                rightArr[i] = temp[i];
       
        merge( leftArr, leftSize, rightArr, rightSize, Array );
}

---

Let's get rid of "Left Array[]" and "Right Array[], in your code. You can't use them, anyway.

You can use Array[] and temp[], and that's it for array's.

Mooon, you have too much code in there! This is a recursive program, so you don't need all that.

but i need them for the merge...
what do u think I should send to the mergesort instead?

Quote:

---

Originally Posted by moooon

but i need them for the merge...
what do u think I should send to the mergesort instead?

---

No, you don't need them for the merge, PLUS your assignment says YOU CAN'T use them.

It's frustrating, but you'll see the beauty of a nice recursive algo, here. When you're done making those changes,
please post THE WHOLE PROGRAM, so I can see EVERYTHING in context.

Didn't answer your question though, did I?

Mergesort will get two int's, a low and a hi index number.

hmm... I think my suggested solution is flawed. The problem is that if you sort the helper array, what do you pass as the helper array when calling mergesort()? Sorting the helper array works if on each recursive call a helper array local to that call is created, but this seems to be beyond the bounds of what is allowed.