Dynamic memory release problem in VS2017

[koce]

Hi, guys,

I did a merge sort function for integers,
it works fine in online compiler,
but crashes in VS2017 at the moment of dynamic memory release.

  static void MergerSort(int* array, int start, int end)
{
	int n = end - start + 1;

	if (n < 2)
	{
		return;
	}

	int n2 = n / 2;

	MergerSort(array, start, start + n2 - 1);

	MergerSort(array, start + n2, end);

	int* Combined = new int[n];
	
	int l = start; //left
	int r = start + n2;//right
	int c = start; //combined

	while (c<=end)
	{
		if (l == start + n2) // left part is finished
		{
			Combined[c++] = array[r++];
		}
		else if (r == end + 1) // right part is finished
		{
			Combined[c++] = array[l++];
		}
		else if (array[l]<array[r])  // both parts have elements for sorting, left is smaller
		{
			Combined[c++] = array[l++];
		}
		else if (array[l] > array[r])  // both parts have elements for sorting, right is smaller
		{
			Combined[c++] = array[r++];
		}
		else    // both parts have elements for sorting, left is equal to right
		{
			Combined[c++] = array[l++];
			Combined[c++] = array[r++];
		}
	}

	for (int i = start; i <= end; ++i)
	{
		array[i] = Combined[i];
	}

	delete[] Combined;  // here is the VS2017 crash

	return;
}

Can someone explain me why VS is doing that?

[Ganado]

Thank you for formatting your code, but can you show the calling code (A minimal, compileable program would be appreciated). I can't immediately tell what's wrong other than possibly out-of-bounds accesses.

Unrelated, but normally I don't expect a sorting algorithm to have to do multiple new[] calls, seems too resource intensive.

[dhayden]

Can someone explain me why VS is doing that?

Or "why is the online compiler doing that?" That's the one that's working by accident here. Your code is buggy.

You fill Combined from start to end. You should fill it from 0 to n-1. Similarly, at line 49 you need to copy from Combined[i-start].

[Repeater]

Your code writes outside the array Combined. You're trashing data and causing damage. That damage exhibits, in this case, when you call delete.

[koce]

Thank you all guys for the help, you were right.
Thank you for the proposed correction - it is right on spot.
I did follow recursive calls more carefully and saw where Combined array is doing it's write and read outside of reserved memory. VS compiler stays silent about that, okay, no warning for writing outside the array bounds. But why then signals on deletion of the reserved memory block? Deletion of something reserved correctly before is nothing to signal about.
Looks like to me as inconsistent warning - " I will warn you not where you disobey the rules, but at a later point." Or it allows you to address incorrectly, but not exactly :)))

This reminds me of a popular female wisdom, mother advises her daughter :
If your husby get home drunk and smilling late at night,
do not fight him, put him to bed, let him sleep and rest.
In the morning when he has the regular headover and is contactable,
that is the right time to start the postponed fight. so he will definately remember the story :)))

Obviously the online compiler also lets me write and read outside silently,
but then allows me to delete. That seems normal, like kind of consistent no warning behaveour.

[Ganado]

Well, out-of-bounds array accesses invoke undefined behavior, so it's just a waste of brain power to try to make sense of it. Undefined behavior doesn't necessarily mean an immediate crash/segfault; anything can happen.

[Repeater]

Obviously the online compiler also lets me write and read outside silently

The compiler can only tell you about syntax errors. Array access is deliberately unchecked. If you use an array, it's up to you to be sure you're doing it correctly.

If you want checked array access, then use a vector and use at instead of [], and be ready to catch the exceptions.

In fact, just use vector anyway. Don't use arrays.

but then allows me to delete.

The compiler did not allow you to delete. When the delete happens, the compiler is no longer involved. At that point, you're running instructions on a processor. All the compiler can do is check that what you wrote obeys the syntax rules of the language. It is up to YOU to be sure that what you're doing is safe. YOU are the programmer. C and C++ trust you to a very large degree; much more than some other programming languagues and environments. With great power comes great responsibilty.

[dhayden]

When you write outside the heap-allocated array, you might be changing other data in the program, or you might be changing the data that the library uses to keep track of the heap. This is called heap corruption and that's what happened here.

Once you've overwritten data tracking the heap, any new or delete could cause the program to crash or otherwise exhibit weird symptoms. So it's like a ticking timebomb. The frustrating part, as you've found, is that the symptom (your crash) usually occurs after the bug (writing out of bounds). Sometimes it occurs long after the bug.

The details of what will happen are implementation dependent. As Ganado said, the bottom line is that the behavior is undefined. There is no "right" thing for the program to do after you access the array out of bounds.