Jump to content

  • Log In with Google      Sign In   
  • Create Account

C# - Merging two sorted arrays - 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.

  • You cannot reply to this topic
9 replies to this topic

#1 PurpleKnives   Members   -  Reputation: 100

Like
0Likes
Like

Posted 04 August 2011 - 01:23 PM

Hey, I'm trying to implement a merge sort in C#. I'm having troubles writing the merging function. There's an error and I can't tell why it happens.
Here's the code: (the algorithm is the usual one - comparing the first two elements in the arrays each time)

        static void Merge(int[] Arr, int left, int mid, int right)
        {
            int[] TempArr = new int[right - left + 1];

            int LeftPtr = left, LeftEnd = mid, RightPtr = mid + 1, RightEnd = right;
            int Index = 0;

            while (LeftPtr <= LeftEnd && RightPtr <= RightEnd)
            {
                if (Arr[LeftPtr] <= Arr[RightPtr])
                    TempArr[Index++] = Arr[LeftPtr++];
                else
                    TempArr[Index++] = Arr[RightPtr++];
            }

            if (RightPtr > RightEnd)
            {
                while (LeftPtr <= LeftEnd)
                    TempArr[Index++] = Arr[LeftPtr++];
            }

            if (LeftPtr > LeftEnd)
            {
                while (RightPtr <= RightEnd)
                {
                    TempArr[Index++] = Arr[RightPtr++]; [b]// This is the error line. It says index was out of range.[/b] 
                }
            }

            for (int i = 0; i < TempArr.Length; ++i)
            {
                Arr[left++] = TempArr[i];
            }

        }

Anyone has an idea where could my problem be?

Thanks for any help.

Sponsor:

#2 skyskewz   Members   -  Reputation: 102

Like
0Likes
Like

Posted 04 August 2011 - 01:58 PM

Hms... arent all those while loops infinite ?



while (RightPtr <= RightEnd)
{
 ....
}

Is always true when it's not altered in the while loop... So it keeps on copying the array until it goes out of range.

Correct me please if i'm wrong.

#3 PurpleKnives   Members   -  Reputation: 100

Like
0Likes
Like

Posted 04 August 2011 - 02:04 PM

But I'm increasing RightPtr (Arr[RightPtr++]). Why would it not stop?

#4 Promethium   Members   -  Reputation: 580

Like
0Likes
Like

Posted 04 August 2011 - 02:48 PM

Are you sure right is inside the array? If for example your call looks like Merge(arr, 0, arr.Count()); then
while (RightPtr <= RightEnd) { TempArr[Index++] = Arr[RightPtr++]; }
will fail when RightPtr == RightEnd.

#5 PurpleKnives   Members   -  Reputation: 100

Like
0Likes
Like

Posted 04 August 2011 - 02:54 PM

Yeah, I'm pretty sure 'right' is inside the array.

This is the recursive call function:

        static void MergeSort(int[] Arr, int left, int right)
        {
            if (left == right)
                return;

            MergeSort(Arr, left, left + (right - left) / 2);
            MergeSort(Arr, left + (right - left) / 2 + 1, right);

            Merge(Arr, left, (right - left) / 2, right);
        }

And this is how I call the function from main:

MergeSort(Arr, 0, Arr.Length - 1);


#6 PurpleKnives   Members   -  Reputation: 100

Like
0Likes
Like

Posted 05 August 2011 - 07:07 PM

Anyone...? :(

#7 Khaiy   Crossbones+   -  Reputation: 1342

Like
0Likes
Like

Posted 06 August 2011 - 01:43 AM

It's late and I'm a little bleary-eyed, so please forgive me if this is mistaken, but I think that Promethium is right.

Might the problem be that

while (RightPtr <= RightEnd)
{
	TempArr[Index++] = Arr[RightPtr++];
}

causes this loop to evaluate when RightPtr = RightEnd, which causes your program to try to access Arr[RightEnd + 1]?

Since the arrays are zero based, if Arr has 10 ints, then (Arr.Length - 1) will pass 9 as an argument for right. But 9 is also the last index you can use that will be in range of the array, as it would be the tenth value. So when the above loop evaluates when RightPtr = RightEnd (in this case, 9) then the block will try to access Arr[9 + 1], which is Arr[10], which doesn't exist.

This would be pretty easy to test with a try catch set, so it is worth at least taking a look at.

#8 a_loho   Members   -  Reputation: 106

Like
1Likes
Like

Posted 06 August 2011 - 03:00 AM

The exception says its your temporary array that is too small. It happens because your mid variable can be lesser than your left variable with your calculation :

instead of

Merge(Arr, left, (right - left) / 2, right);


it should be

Merge(Arr, left, left + (right - left) / 2, right);


#9 PurpleKnives   Members   -  Reputation: 100

Like
0Likes
Like

Posted 06 August 2011 - 08:11 AM

Thank you, a_loho - it worked! :D

Thanks everyone who helped. :)

I have a question - is there a way to implement merge sort without using the extra memory?

#10 iMalc   Crossbones+   -  Reputation: 2306

Like
0Likes
Like

Posted 06 August 2011 - 02:40 PM

Yes there is. std::stable_sort typically does this. If you take a look at how it's implemented in the std C++ library then you'll see how they do it.
I remember that it involves using the GCD.

Or if you don't do that, you're better off allocating the second array as the same size as the input array just once at the start of the merge. You need an array that large for the final merge anyway, so just allocate that much up front and be done with it instead of also allocating all these tiny little arrays as well.
I also highly recommend that you alter the meaning of the ranges to include the leftmost but not the rightmost item. This means you can just pass Arr.Length instead of Arr.Length - 1, and you may find lots of other places where you'd no longer have to add or subtract 1, and it becomes a bit tidier and simpler.
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms




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.



PARTNERS