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