# Merge Sort in C++

This code demonstrates merge sort implemented in C++. Notice the use of a wrapper function to dynamically allocate the requisite scratch space.

Back to the merge sort tutorial
```/* Helper function for finding the max of two numbers */
int max(int x, int y)
{
if(x > y)
{
return x;
}
else
{
return y;
}
}

/* left is the index of the leftmost element of the subarray; right is one
* past the index of the rightmost element */
void merge_helper(int *input, int left, int right, int *scratch)
{
/* base case: one element */
if(right == left + 1)
{
return;
}
else
{
int i = 0;
int length = right - left;
int midpoint_distance = length/2;
/* l and r are to the positions in the left and right subarrays */
int l = left, r = left + midpoint_distance;

/* sort each subarray */
merge_helper(input, left, left + midpoint_distance, scratch);
merge_helper(input, left + midpoint_distance, right, scratch);

/* merge the arrays together using scratch for temporary storage */
for(i = 0; i < length; i++)
{
/* Check to see if any elements remain in the left array; if so,
* we check if there are any elements left in the right array; if
* so, we compare them.  Otherwise, we know that the merge must
* use take the element from the left array */
if(l < left + midpoint_distance &&
(r == right || max(input[l], input[r]) == input[l]))
{
scratch[i] = input[l];
l++;
}
else
{
scratch[i] = input[r];
r++;
}
}
/* Copy the sorted subarray back to the input */
for(i = left; i < right; i++)
{
input[i] = scratch[i - left];
}
}
}

/* mergesort returns true on success.  Note that in C++, you could also
* replace malloc with new and if memory allocation fails, an exception will
* be thrown.  If we don't allocate a scratch array here, what happens?
*
* Elements are sorted in reverse order -- greatest to least */

int mergesort(int *input, int size)
{
int *scratch = (int *)malloc(size * sizeof(int));
if(scratch != NULL)
{
merge_helper(input, 0, size, scratch);
free(scratch);
return 1;
}
else
{
return 0;
}
}
```
Back to the merge sort tutorial