C++ implementation of merge sort

Question

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

Answer 1

• 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<=.

Answer 2

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++]));

Answer 3

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);