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;
if (RightPtr > RightEnd)
{
while (LeftPtr <= LeftEnd)
TempArr[Index++] = Arr[LeftPtr++];
}
if (LeftPtr > LeftEnd)
{
while (RightPtr <= RightEnd)
{
TempArr[Index++] = Arr[RightPtr++]; // This is the error line. It says index was out of range.
}
}
for (int i = 0; i < TempArr.Length; ++i)
{
Arr[left++] = TempArr;
}
Are you sure right is inside the array? If for example your call looks like [color="#660066"][font="CourierNew, monospace"]Merge(arr, 0, arr.Count());[/font][font="Arial"] then [/font]
[color="#000088"]while [color="#666600"]([color="#660066"]RightPtr [color="#666600"]<= [color="#660066"]RightEnd[color="#666600"]) [color="#666600"]{ [color="#660066"]TempArr[color="#666600"][[color="#660066"]Index[color="#666600"]++] [color="#666600"]= [color="#660066"]Arr[color="#666600"][[color="#660066"]RightPtr[color="#666600"]++]; [color="#666600"]}
[color="#666600"]will fail when RightPtr == RightEnd.
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.
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);
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="#666600"].[color="#660066"]Length instead of [color="#660066"]Arr[color="#666600"].[color="#660066"]Length [color="#666600"]- [color="#006666"]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.
