Sign in to follow this  
ZivBenShitrit

C# - Merging two sorted arrays - merge sort

Recommended Posts

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)

[CODE]
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];
}

}
[/CODE]

Anyone has an idea where could my problem be?

Thanks for any help.

Share this post


Link to post
Share on other sites
Hms... arent all those while loops infinite ?



[code]while (RightPtr <= RightEnd)
{
....
}[/code]

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.

Share this post


Link to post
Share on other sites
Are you sure right is inside the array? If for example your call looks like [color="#660066"][font="CourierNew, monospace"][size="2"]Merge(arr, 0, arr.Count());[/size][/font][/color][size="2"][font="Arial"] then [/font][/size]
[color="#000088"]while[/color] [color="#666600"]([/color][color="#660066"]RightPtr[/color] [color="#666600"]<=[/color] [color="#660066"]RightEnd[/color][color="#666600"])[/color] [color="#666600"]{[/color] [color="#660066"]TempArr[/color][color="#666600"][[/color][color="#660066"]Index[/color][color="#666600"]++][/color] [color="#666600"]=[/color] [color="#660066"]Arr[/color][color="#666600"][[/color][color="#660066"]RightPtr[/color][color="#666600"]++];[/color] [color="#666600"]}[/color]
[color="#666600"]will fail when RightPtr == RightEnd.[/color]

Share this post


Link to post
Share on other sites
Yeah, I'm pretty sure 'right' is inside the array.

This is the recursive call function:

[code]
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);
}
[/code]

And this is how I call the function from main:

[code] MergeSort(Arr, 0, Arr.Length - 1);[/code]

Share this post


Link to post
Share on other sites
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

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

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.

Share this post


Link to post
Share on other sites
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

[code]Merge(Arr, left, (right - left) / 2, right);[/code]


it should be

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

Share this post


Link to post
Share on other sites
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 [color="#660066"]Arr[/color][color="#666600"].[/color][color="#660066"]Length[/color] instead of [color="#660066"]Arr[/color][color="#666600"].[/color][color="#660066"]Length [color="#666600"]-[/color] [/color][color="#006666"]1[/color], 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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this