C++11 merge sort implementation

Question

I've tried implementing merge sort in C++ just by looking at this Wikipedia graphic. Comparing my code to other merge sort code implementations, it doesn't look quite the same at first glance. Have I done it in an acceptable way? How can it be improved, particularly using modern C++?

#include <iostream>
#include <deque> // using deque for `pop_front`
#include <random>
std::deque<int> mergeChunks(std::deque<int> &a, std::deque<int> &b);
std::deque<int> mergeSort(const std::deque<int> &d) {
 std::deque<std::deque<int>> chunks; // in the end, the first element will be the sorted list
 for (const auto &a : d) {
 // add each element of `v` to `chunks` as its own chunk
 chunks.push_back({ a });
 }
 while (chunks.size() > 1) {
 std::deque<std::deque<int>> tmp; // this will be the new set of chunks at the end of this iteration
 for (auto i = 0; i < chunks.size() - 1; i += 2) {
 tmp.push_back(mergeChunks(chunks[i], chunks[i + 1]));
 }
 // if there is an odd number of elements, then add the one that was missed in the for loop to `tmp`
 if (chunks.size() % 2 == 1) {
 tmp.push_back(chunks[chunks.size() - 1]);
 }
 chunks = tmp;
 }
 return chunks[0];
}
std::deque<int> mergeChunks(std::deque<int> &a, std::deque<int> &b) {
 std::deque<int> ret;
 while (true) {
 // if all the elemnts of one chunk have been added to `ret` then add the remaining 
 // elements of the other chunk to the end of `ret` (knowing that they're sorted)
 if (a.size() == 0) {
 ret.insert(ret.end(), b.begin(), b.end());
 return ret;
 }
 if (b.size() == 0) {
 ret.insert(ret.end(), a.begin(), a.end());
 return ret;
 }
 // always comparing the first elements of each chunk. After an element is added
 // to `ret`, pop it from the chunk
 if (a[0] < b[0]) {
 ret.push_back(a[0]);
 a.pop_front();
 }
 else {
 ret.push_back(b[0]);
 b.pop_front();
 }
 }
 return ret; // never reached
}
int main() {
 auto list = mergeSort({ 8, 7, 6, 5, 4, 3, 2, 1 });
}

Answer 1

• Looks like a good bottom-up merge. A bit heavy on the memory at the first glance though.

• if (a[0] < b[0]) loses stability. The main advantage of the merge sort is is that it retains the order of elements which compare equal (for sorting integers it is irrelevant, but think of sorting structures). Your code merges b[0] first. Consider a[0] <= b[0] instead.

• Handling the unlikely conditions such as a.size() == 0 and b.size() == 0 better be done outside of the loop. Consider instead

  while (a.size() > 0 && b.size() > 0) {
   do_actual_merge();
  }
  ret.insert(ret.end(), a.begin(), a.end()); // No-op if a.size() == 0
  ret.insert(ret.end(), b.begin(), b.end()); // No-op if b.size() == 0
  return ret;
  

• I am not sure that chunks.size() % 2 == 1 is the best way to express your intentions. I'd go for i < chunks.size(), even though it lifts a declaration of i out of the loop.

• Loki Astari: Basically everything I would have said. I would have added a bit about using an interface that has iterators so as to be more idiomatic C++.