Merge sort implementation efficiency

Question

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

• Loki Astari: Have a look at: codereview.stackexchange.com/a/88373/507

Answer 1

Not a merge sort

This step in the merge() function:

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

is an \$O(N^2)\$ operation and works more like an insertion sort or bubble sort rather than a merge. Also, you should only have to merge once instead of four times. The pseudocode for the mergesort function should be:

mergesort(leftHalf);
mergesort(rightHalf);
merge(leftHalf, rightHalf);

I believe your merge function is not only slow but also doesn't merge properly in one pass, which is why your program seems to require calling it four times.