Mergesort in C++

I'm flexing the C++ muscle and came up with the following implementation of Mergesort. Any suggestions as to the implementation and style are welcome.

int* MergeSort(int a[], int size)
{
if (size <= 1) return a;
int mid_point = size / 2;
int left_size = mid_point;
int right_size = size - mid_point;

int *left_half = new int[left_size];
int *right_half = new int[right_size];

for (int ndx = 0; ndx < left_size; ++ndx )
left_half[ndx] = a[ndx];
for (int ndx = mid_point, ndx2 = 0; ndx < size; ++ndx, ++ndx2 )
right_half[ndx2] = a[ndx];

int *left = MergeSort(left_half, left_size);
int *right = MergeSort(right_half, right_size);

return Merge(left, left_size, right, right_size);
}

int* Merge(int left[], int size_left, int right[], int size_right)
{
int *result = new int[size_left + size_right];
int i = 0, j = 0, k = 0;
while (i < size_left && j < size_right)
{
if (left[i] < right[j])
result[k++] = left[i++];
else
result[k++] = right[j++];
}
while (i < size_left)
result[k++] = left[i++];
while (j < size_right)
result[k++] = right[j++];

delete left;
delete right;

return result;
}


Style

This is not C++.

It is C. The only think you are using the C++ compiler for is new and delete and you may as well just use malloc. So this is not the way we use new/delete in C++.

Memory management.

Your code is not exception safe.

You don't do resource management using pointers. You do it using objects. You then get the constructor to allocate the resource and the destructor to deallocate the resource.

// In C
{
int*  data = new int[10];

// do stuff with data.

delete [] data;
}

// In C++
{
Container   data;      // container allocates space for int array.

// do stuff with data.
}                          // destructor deallocates space for int array
// Note: Even if there is an exception.


Iterators

You don't pass arrays around in C++. You pass iterators. Thus allowing you to re-use your algorithm with different types of containers (arrays/vectors/C-Arrays/strings/lists etc).

Also passing arrays to functions is dangerous and involves humans getting things correct. This is because arrays decay to pointers. Thus getting the size of the array correct involves humans doing the correct thing to work out the size (which is error prone).

Pointers.

You should not be using pointers. The semantics of ownership are not clear. Who owns the pointer (and thus is responsible for deleting it). Memory should either be managed by a container, passed by smart pointer to transfer ownership or passed by reference to retain ownership.

Code Review.

So what is the interface here?

int* MergeSort(int a[], int size)


You pass in an array but you return a pointer. Is this a pointer to the input array or are you returning dynamically allocated memory or is it some internal array. Am I supposed to free the returned pointer. I have no idea.

We have objects that will do this for you.
Not only that they will copy the content when they are created.

    int *left_half = new int[left_size];
int *right_half = new int[right_size];

for (int ndx = 0; ndx < left_size; ++ndx )
left_half[ndx] = a[ndx];
for (int ndx = mid_point, ndx2 = 0; ndx < size; ++ndx, ++ndx2 )
right_half[ndx2] = a[ndx];

// Much easier to write.
std::vector<int>   left(a, a + left_size);
std::vector<int>   right(a + left_size, a + size);


Please one variable per line. Also use names that make the code easy to read and maintain. Its easy for you as you just wrote it. But I have to read and decipher it would make my life as a maintainer easier if I can glean some context from the names of the variables you use.

    int i = 0, j = 0, k = 0;


This can be simplified:

        if (left[i] < right[j])
result[k++] = left[i++];
else
result[k++] = right[j++];
}

// Easier to read and write as
result[k++] = (left[i] < right[j])
? left[i++]
: right[j++];


Also be using the less than (rather than less than or equals) you merge sort is not stable. Stability of the algorithm is sometimes nice to have.

Prefer to use braces around sub statements.
There are corner cases where it makes a difference.

    while (i < size_left)
result[k++] = left[i++];
while (j < size_right)
result[k++] = right[j++];


Don't use a loop when an algorithm will do the work for you.

while (j < size_right)
result[k++] = right[j++];

std::copy(right + j, right + size_right, result + k);


This is a bug.

delete left;
delete right;


This is not how you release an array of values.

How I would write it:

mergeSort

template<typename I>
void mergeSort(I begin, I end)
{
std::size_t   size = std::distance(begin, end);
if (size <= 1) {
return;
}

std::size_t   half = size/2;

I   mid = begin;

mergeSort(begin, mid);
mergeSort(mid, end);

merge(begin, mid, end);
}


merge

template<typename I>
void merge(I begin, I mid, I end)
{
typedef typename std::iterator_traits<I>::value_type   value_type;

std::vector<value_type>    left(begin, mid);
std::vector<value_type>    right(mid, end);

auto leftIter  = std::begin(left);
auto leftEnd   = std::end(left);

auto rightIter = std::begin(right);
auto rightEnd  = std::end(right);

auto dest      = begin;

while(leftIter != leftEnd && rightIter != rightEnd) {

(*dest) = (*leftIter <= *rightIter)
? *leftIter++
: *rightIter++;
++dest;
}
dest = std::copy(leftIter, leftEnd, dest);
dest = std::copy(rightIter, rightEnd, dest);
}


mergeSort utility. Pass a container (vector/array/list/C-Array etc)

template<typename C>
void mergeSort(C& container)
{
mergeSort(std::begin(container), std::end(container));
}


Optimization

Looking at this a bit longer there are a couple of optimizations I could do.

    std::vector<value_type>    left(begin, mid);
// std::vector<value_type>    right(mid, end);  don't actually need this.
The code will work without
making this copy. Just
appropriately.


You should also use std::move() to force movement on types where it would help.

    // The initial copy.
std::vector<value_type>    left(std::make_move_iterator(begin),
std::make_move_iterator(mid));

// When moving stuff back
(*dest) = std::move((*leftIter <= *rightIter)
? *left++
: *right++);

• @Daniel There is also std::merge and even std::inplace_merge which would make the implementation almost trivial. Of course "flexing the C++ muscle" doesn't work if you "cheat" like that, but you should be aware that you can and probably should.
– nwp
Nov 17 '15 at 21:22
• @twohundredping, please comment if there are errors in an answer that isn't yours, rather than trying to edit. It both alerts the answerer that they made a mistake and allows them to change the code if need be. In this specific case, I don't see any harm in it, but in general, you should avoid it.
– Nic
Nov 20 '15 at 0:19