Merge sort implementation efficiency

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
#include

template
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 *(f2 + j)) {
std::iter_swap(f1 + i, f2 + j);
}
}
}
}
}

template
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()
{

Not a merge sort

This step in the merge() function:

for (size_t i = 0; 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.

StackExchange Code Review Q#123976, answer score: 4