A question regarding a debug error.

[LarryChen]

Here is the code,

void MergeArray(int arr[], int l, int m, int r)
{
	int* b = new int[r-1+1];

	int i, j;

	int index = 0;
	for(i=l, j=m+1;i<=m && j<=r;)
	{
		if(arr[i]<arr[j])
		{
			b[index] = arr[i++];
			index++;
		}
		else
		{
			b[index] = arr[j++];
			index++;
		}
	}

	if(i>m)
	{
		while(j<=r)
		{
			b[index] = arr[j++];
			index++;
		}
	}
	else
	{
		while(i<=m)
		{
			b[index] = arr[i++];
			index++;
		}
	}

	index = 0;
	for(i=l;i<=r;++i)
	{
		arr[i] = b[index];
		index++;
	}

	delete[] b;
}

void MergeSort(int arr[], int l, int r)
{
	if(l>=r)
		return;

	int m = (l+r)/2;

	MergeSort(arr, l, m);
	MergeSort(arr, m+1, r);

	MergeArray(arr, l, m, r);
}

void MergeSort(int arr[], int size)
{
	MergeSort(arr, 0, size-1);
}

int main()
{
	int arr[] = { 4, 1, 22, 5, 12, 9, 13, 19, 3};

	MergeSort(arr, 9);
	return 0;
}

Actually, there is a debug error related to the pointer b defined in MergeArray. If I change the original statement int* b = new int[r-1+1] to int* b = new int[r-1+2], then it will fix the problem. So obviously b is referenced with an index out of boundary, but I couldn't find out where it happens. Thanks.

[Arjay]

When you step through the code in the debugger (like you always do before posting to the forum, right?), what is the passed in value of r and why is it out of bounds?

[2kaud]

You are effectively changing

int* b = new int[r];

to

int* b = new int[r + 1];

for(i=l, j=m+1;i<=m && j<=r;)
	{
		if(arr[i]<arr[j])

The condition is j <= r. As arrays are indexed starting at 0, should your conditions be 'less than' rather than 'less than or equal'? What are l, m and r used?

[Eri523]

Just a marginal remark, adding to what the two other contributors already posted correctly: You started this thread in the wrong forum section; your code quite obviously is native C++, not C++/CLI (AKA managed C++), so this thread would be correctly placed in the C++ (non-MS VC) section. Perhaps a moderator can move the thread.

(Actually, it's way more common that mistakenly threads about C++/CLI get started in one of the native C++-related sections than the other way round like here.)