Merge Sort Heap Corruption Detected

Question

I am writing a function that is supposed to sort an array using merge sorting. So far I have the two functions:

template <typename Item, typename SizeType>
void merge_sort(Item data[], SizeType size) {
SizeType size1, size2;
if(size > 1) {
    size1 = size/2;
    size2 = size - size1;
    merge_sort(data,size1);
    merge_sort((data+size1),size2);

    merge(data,size1,size2);
}
}

and:

template <typename Item, typename SizeType>
void merge(Item data[], SizeType size1, SizeType size2) {
Item* temp;
SizeType copied = 0;
SizeType copied1 = 0;
SizeType copied2 = 0;

temp = new Item[size1 + size2];

while(copied1 < size1 && copied2 < size2) {
    if(data[copied1] < (data + size1)[copied2])
        temp[++copied] = data[++copied1];
    else
        temp[++copied] = (data + size1)[++copied2];
}

while (copied1 < size1)
    temp[++copied] = data[++copied1];
while (copied2 < size2)
    temp[++copied] = (data + size1)[++copied2];

for(SizeType i = 0; i < size1 + size2; ++i)
    data[i] = temp[i];
delete [] temp;
}

When I try to run the program however, I get a debug error saying that the heap is corrupted after a normal block and that CRT detected that the application wrote to memory after the end of the heap buffer. Can anyone explain what this means and how I could fix it?

Answer 1

You're incrementing before using the values... so that basically makes the checks obsolete...

use copied++ instead.

You need the post-increment operator, because if you increment it before you use it, you get out of bounds. Increment and decrement operators

Answer 2

Do you mean for your increments to be post-increments rather than pre-increments? For example:

    temp[copied++] = (data + size1)[copied2++];

With pre-increment, on the first iteration, when copied2 was 0, you were accessing (data + size1)[1]. When copied2 reaches the end of your allocated memory, you are accessing one past the end.

To avoid this, I recommend not having increments as subexpressions. It can be confusing to write and to read.

Answer 3

if copied = 0 and copied1 = 0 then line

temp[++copied] = data[++copied1];

will produce

temp[1] = data[1];

because prefix ++ has the highest priority here