Design
int main() {
vector<int> a = {3, 0, 7, 5, 7, 8, 3, 1};
printArray(mergeSort<vector<int>>(a.begin(), a.end()));
return 0;
}
My problem here is that you have to specify the type as part of the name of the function mergeSort<vector<int>>(). It would be much nicer if the compiler could work out the type for you, this would make modifying the code much easier in the long run.
In the above code if I change the type of a then I also need to change the type of mergeSort<vector<int>>(). In certain situations this could cause issues when coupled with auto-conversion.
I also dislike that you create a new container as a result of the sort. Why not sort in-place. A sort in-place can be used in conjunction with a copy to create a newly sorted container (but not the other way around).
Also your way of doing the sort allocates a lot of small arrays dynamically. This is very expensive. It would be better if you could allocate a temporary buffer that can be re-used by the sorting code.
The last thing in the design is that you use a single function to do all the work. In self documenting code it is much nicer to break your code into short self named (and thus explained) operations.
Code Review
Namespace using
Please don't do this:
using namespace std;
Thx! I never use "using namespace std;" for real code, this was just an exercise for myself, that's also why I wanted to implement merge for myself.
Thats not a good excuse. The trouble with doing it for small programs is that it becomes a reflex and you then accidentally do it all the time. Best not to form bad habits in the first place.
Also this code (if it had reviewed well) could have just been copied into a larger project and then polluted it.
Using const reference consistency.
Can you spot the issue here?
template<typename T>
void printArray(const T& a) {
for (auto i: a) {
cout << i << " ";
}
cout << endl;
}
What about i. Every iteration of the loop you are copying the value out of the container into the variable i. This is fine for POD or simple types. But what about complex types (or expensive to copy types).
for (auto const& i: a) {
// ^^^^^^
cout << i << " ";
}
Assumptions Kill Generic abilities.
This assumes that the iterators are Random Access Iterators.
auto n = end - begin;
You could use std::distance() this will allow you to find the count in the most efficient way no matter what the type of the iterator.
You only use Copy Semantics
Your merge moves the objects between containers using copy semantics.
merged.push_back(*firstIt);
Since C++11 we have had move semantics. This (move) is never more expensive than a copy and usually much more efficient than a copy. None of your intermediate arrays are re-used. So there is no need to preserve the data in these intermediate containers. So you should be using move semantics when moving the objects internally.
Use standard algorithms were they are available.
while(firstIt != firstHalf.end()) {
merged.push_back(*firstIt);
++firstIt;
}
This is obviously a copy.
std::copy(firstIt, firstHalf.end(), std::back_inserter(merged));
Example
#include <vector>
#include <iterator>
#include <algorithm>
#include <utility>
#include <iostream>
template<typename I, typename BI>
void mergeTogether(I begin, I mid, I end, BI beginBuffer)
{
I low = begin;
I hig = mid;
BI buf = beginBuffer;
while(low < mid && hig < end) {
if (*low <= *hig) {
std::iter_swap(low, buf);
++low;
}
else {
std::iter_swap(hig, buf);
++hig;
}
++buf;
}
std::move(low, mid, buf);
std::move(hig, end, buf);
std::size_t size = std::distance(begin, end);
std::move(beginBuffer, std::next(beginBuffer, size), begin);
}
template<typename I, typename BI>
void mergeSortUsingBuffer(I begin, I end, BI beginBuffer)
{
std::size_t size = std::distance(begin, end);
if (size < 2) {
return;
}
std::size_t split = size/2;
I mid = std::next(begin, split);
BI midBuffer = std::next(beginBuffer, split);
mergeSortUsingBuffer(begin, mid, beginBuffer);
mergeSortUsingBuffer(mid, end, midBuffer);
mergeTogether(begin, mid, end, beginBuffer);
}
template<typename I>
void mergeSort(I begin, I end)
{
using ValueType = typename std::iterator_traits<I>::value_type;
std::size_t size = std::distance(begin, end);
std::vector<ValueType> buffer(size);
mergeSortUsingBuffer(begin, end, std::begin(buffer));
}
int main()
{
std::vector<int> a = {3, 0, 7, 5, 7, 8, 3, 1};
mergeSort(std::begin(a), std::end(a));
std::copy(std::begin(a), std::end(a),
std::ostream_iterator<int>(std::cout, ", "));
std::cout << "\n";
}
