# C++ implementation of merge sort

I am studying the merge sort algorithm and implemented it. In the mergeSort function, I am allocating two new vectors. Can I do it without allocating extra memory? Are there any other suggestions?

#ifndef MERGE_SORT
#define MERGE_SORT
#include <vector>

template<typename T>
void merge(std::vector<T>& array, std::vector<T> left, std::vector<T> right) {
array.clear();
auto lsize = left.size();
auto rsize = right.size();
unsigned int i=0, j=0;
while (i < lsize && j < rsize) {
if (left[i] < right[j]) {
array.push_back(left[i]);
++i;
}else {
array.push_back(right[j]);
++j;
}
}
for(; i<lsize; ++i)
array.push_back(left[i]);
for(; j<rsize; ++j)
array.push_back(right[j]);
}

template<typename T>
void mergeSort(std::vector<T>& seq) {
auto n = seq.size();
if (n > 1) {
auto start = seq.begin();
auto end = seq.end();
auto middle = start + n / 2;
std::vector<T> left(start, middle);
std::vector<T> right(middle, end);
mergeSort(left);
mergeSort(right);
merge(seq, left, right);
}
}

#endif // MERGE_SORT


• Can I do it without allocating extra memory?

In fact, yes. The trick is to merge recursively (technically, the $O(\log N)$ extra memory is still necessary for recursion). Here is a pseudo-code for the classic in-place merge:

// Prerequisite: [begin, mid) and [mid, end) ranges are sorted
inplace_merge(begin, mid, end)
{
if (end - begin) < 2) return;

left = begin + (mid - begin)/2;
right = lower_bound(mid, end, *left);

mid = rotate(left, mid, right);

inplace_merge(begin, left, mid);
inplace_merge(mid, right, end);
}

• Stability

The most important feature of merge sort is stability: the elements compared equal retain their original order (not very important for integers, but immensely important when sorting structured data). Your implementation loses it:

if (left[i] < right[j]) {
array.push_back(left[i]);
++i;
}else {
array.push_back(right[j]);
++j;
}


In case of equality it is an element from right to be pushed first. Easy to fix with

if (right[j] < left[i])


or

if (left[i] <= right[j])


First way is preferred, because it doesn't assume existence of operator<=.

• Forgot totally about stability. +1 – Martin York Oct 12 '15 at 23:47

Can I do it without allocating extra memory?

Probably not.
But you can do it without allocating as much memory.

Here:

    std::vector<T> left(start, middle);
std::vector<T> right(middle, end);
mergeSort(left);


So you have just allocated as much space as the original. So we are at 2n. But then you make a recursive call. Which will do exactly the same thing (but with half the array). So we are at 2.5n then you will recursively call it again. Eventually you will allocate a total of 3n space (plus control structures).

An easy way to get around this is to make your interface allocate the scratch array then call your internal merge sort passing the original and a scratch area. So the total amount of space you will use is 2n (and only one extra control structure).

template<typename T>
void mergeSort(std::vector<T>& seq) {

std::vector<T>  scratch(std::begin(seq), std::end(seq));
mergeSortWithScratch(std::begin(seq), std::end(seq),
std::begin(scratch), std::end(scratch));
}

template<typename I>
void mergeSortWithScratch(I beginData, I endData, I beginScratch, I endScratch) {
auto n = std::distance(beginData, endData);
if (n > 1) {
auto middleData     = beginData;     std::advance(middleData,   n/2);
auto middelScratch  = beginScratch;  std::advance(beginScratch, n/2);

mergeSort(beginData, middelData, beginScratch, middelScratch);
mergeSort(middelData, endData, middelScratch, endScratch);
merge(beginScratch, middleScratch, endScratch, beginData);
}
}


Slightly simpler way of writing:

    if (left[i] < right[j]) {
array.push_back(left[i]);
++i;
}else {
array.push_back(right[j]);
++j;
}


Use the trinary expression.

   array.push_back(left[i] < right[j]
? left[i++]
: right[j++]);


The next thing to look at (if you have C++1) is move semantics. These are generally at least as fast as copy but can be a lot quicker for non POD types.

    array.emplace_back(std::move(left[i] < right[j]
? left[i++]
: right[j++]));

• thanks for the info. Why you use auto middle = begin;std::advance(middle, n/2) ? Is there any benefit using the std::advance? Also instead vector.begin() / end() why u use std::begin / end ?. Thanks – gosom Oct 12 '15 at 7:59
• Because all standard algorithms are based on iterators. So I am used to writing my code in terms of iterators. Thus std::begin() and std::end() can also be applied to arrays (or other containers). Thus it allows my code to be container agnostic (when this is useful) at no extra cost. With a slight tweak the above would work for arrays and vectors and C-Arrays or any container that supported random access iterators. – Martin York Oct 12 '15 at 23:43

The way you have implemented this (recursively), it's hard to avoid the vector allocations. Indeed, this can be expensive, as you're potentially doing O(logn) vector allocations. What you can try instead is replacing the vector with a hand-written linked list. There's also an in-place merge sort algorithm that you can realize by carefully swapping elements, and maintaining only 1 extra buffer vector.

There are other implicit vector copies that you can avoid though:

void merge(std::vector<T>& array,
std::vector<T> left,
std::vector<T> right);


You should replace this with the following to prevent copying left and right on every function call.

void merge(std::vector<T>& array,
const std::vector<T>& left,
const std::vector<T>& right);