I made a merge sort implementation in C++, which I have tested with the values:
6, 38, 27, 7, 12, 58, 92, 43, 3, 9, 82, 10
producing the correct output of:
3 6 7 9 10 12 27 38 43 58 82 92
However, when running my program, it seemed pretty slow, and I was wondering if there were any places in my code where there is an inefficiency, or if the entire implementation (recursive in most places, but iterative in parts of the merging) is the wrong way forward.
#include <iostream>
#include <vector>
template<typename InputIt>
void merge(InputIt f1,
InputIt l1,
InputIt f2,
InputIt l2)
{
size_t d1 = std::distance(f1, l1),
d2 = std::distance(f2, l2);
if (d1 == 1 && d2 == 1 && *f1 > *f2) {
std::iter_swap(f1, f2);
}
else {
for (size_t i = 0; i < d1; ++i) {
for (size_t j = 0; j < d2; ++j) {
if (*(f1 + i) > *(f2 + j)) {
std::iter_swap(f1 + i, f2 + j);
}
}
}
}
}
template<typename InputIt>
void merge_sort(InputIt first,
InputIt last)
{
size_t dist = std::distance(first, last);
size_t left = (size_t)(dist / 2);
size_t right = dist - left;
//traverse left
if (left > 1) {
merge_sort(first, first + left);
}
//furthest left point found, merge upwards
merge(first, first + left, first + left, last);
//ensure that all the way right (limited to left section) has been reached
if (right > 1) {
merge_sort(first + left, last);
}
//furthest right point in left section found, merge upwards
merge(first, first + left, first + left, last);
//traverse right
if (right > 1) {
merge_sort(first + left, last);
}
//furthest right point found, merge upwards
merge(first, first + left, first + left, last);
//ensure that all the way left (limited to right section) has been reached
if (left > 1) {
merge_sort(first, first + left);
}
//furthest left point in right section found, merge upwards
merge(first, first + left, first + left, last);
}
int main()
{
std::vector<int> v{6, 38, 27, 7, 12, 58, 92, 43, 3, 9, 82, 10};
merge_sort(v.begin(), v.end());
for (auto& x : v) {
std::cout << x << " ";
}
std::cout << std::endl;
getchar();
}