How to Implement Merge Sort Algorithm in C++

1. Implement Merge Sort for the std::vector Container in C++
2. Analyze Merge Sort Complexity with Empirical Timing Measurements

This article will introduce how to implement a merge sort algorithm in C++.

Implement Merge Sort for the std::vector Container in C++

Merge sort utilizes the divide and conquer strategy to reach efficiency, and it can be used as the general-purpose sorting algorithm for large lists. The idea behind the algorithm is to divide the input vector into multiple smaller vectors and then sort each of those vectors. Once the smaller vectors are done, we can merge them into a single list which happens to be a relatively more straightforward operation. Note that the following code example implements this method using the recursion as it’s optimally suited for this solution. A recursive process is used to divide the original vector multiple times until we get the two-element vectors, where the comparison function will be called. When each pair is sorted, they are merged into four-element vectors and so on until the final level of recursion returns.

The mergeSort function is the core part of the recursive process. It takes vector reference as the only argument and checks if the size is less than equal to one. If so, the vector qualifies as a sorted one, and the function returns. When the vector contains two or more elements, it gets split into two separate vector objects, and the mergeSort function is called on each of them. Notice that the latter part forces the sorting to begin on the smallest subvectors. Once the recursion reaches such level, both mergeSort functions return, and the following code starts execution. At first, the vec vector is cleared, and then the merge function is called. merge function is implemented with an iterative process that can be grokked with close observation. In general, the latter step joins the smallest sorted vectors into one vector object.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void merge(vector<T> &vec, vector<T> &v1, vector<T> &v2) {
  auto siz1 = v1.size();
  auto siz2 = v2.size();
  size_t p1 = 0;
  size_t p2 = 0;

  while (p1 < siz1 && p2 < siz2) {
    if (v1.at(p1) < v2.at(p2))
      vec.push_back(v1.at(p1++));
    else
      vec.push_back(v2.at(p2++));
  }

  while (p1 < siz1) vec.push_back(v1.at(p1++));
  while (p2 < siz2) vec.push_back(v2.at(p2++));
}

template <typename T>
void mergeSort(vector<T> &vec) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort(v1);
  mergeSort(v2);

  vec.clear();
  merge(vec, v1, v2);
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  mergeSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Alternatively, one could rewrite the previous code using the STL std::merge algorithm that could simplify the code for reading. Note that, std::merge function substitutes our merge implementation, and vector merging can be accomplished with a single statement in the mergeSort function body. When the final level of recursion returns two vectors in the first call of mergeSort, the last invocation of std::merge will store the sorted contents in the original vec object that can be observed from the main function.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void mergeSort2(vector<T> &vec) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort2(v1);
  mergeSort2(v2);

  vec.clear();
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
             std::back_inserter(vec));
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  mergeSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Analyze Merge Sort Complexity with Empirical Timing Measurements

Merge sort offers O(nlogn) worst-case running time, which happens to be one of the best among the contemporary general-purpose sorting algorithms. It has the linear space complexity in a worst-case scenario that is more than the quick sort algorithm offers. The latter one tends to be relatively faster in practice when the implementation utilizes efficient methods for choosing the pivot variable.

Even though the recursive method can be pretty tricky to comprehend, one can always use a debugger for diving into the nitty-gritty of each step. On the higher level, though, we can use the following code sample to count the recursive function invocations between different vector sizes. Notice that the sum of recursive calls tends to be the function - 2n - 2 where n corresponds to the number of elements in the vector.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void mergeSort2(vector<T> &vec, int &level) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort2(v1, ++level);
  mergeSort2(v2, ++level);

  vec.clear();
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
             std::back_inserter(vec));
}

int main() {
  vector<int> vec3(100, 10);
  vector<int> vec4(200, 10);

  int recursion_level = 0;

  mergeSort2(vec3, recursion_level);
  cout << "recursion level: " << recursion_level << endl;

  recursion_level = 0;
  mergeSort2(vec4, recursion_level);
  cout << "recursion level: " << recursion_level << endl;

  return EXIT_SUCCESS;
}

Output:

recursion level: 198
recursion level: 398