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