Merge sort algorithm implementation using C++ (redux)

Question

This is a follow up question to the one I asked a couple of days ago.

---

I reviewed the suggestions & did some research (specifically, read relevant info on CLRS). The new version is 3 times faster (210ms vs 71ms on 100,000 numbers) & looks cleaner.

One thing I still feel weird about is not using iterators except than to init the sub-vectors. However, any attempt in using them causes a drop in performance (down to 120ms).

I'm also curious if my code is good in terms of code style. Is this idiomatic C++?

void merge(std::vector<int>& a, int p, int q, int r)
{
    std::vector<int> l(a.begin() + p, a.begin() + q + 1);
    std::vector<int> ri(a.begin() + q + 1, a.begin() + r + 1);

    int n1 = q - p + 1;
    int n2 = r - q;

    int i, j; i = j = 0;

    while (i < n1 && j < n2) {
        if (l[i] < ri[j]) {
            a[p++] = l[i++];
        } else {
            a[p++] = ri[j++];
        }
    }

    while (i < n1) {
        a[p++] = l[i++];
    }

    while (j < n2) {
        a[p++] = ri[j++];
    }
}

void merge_sort(std::vector<int>& a, int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

Answer 1

Let's do this in steps. This is going to be a longer answer, but I'll try this experiment at least once. The original version takes about 400 ms to sort 1E6 integers on my machine (virtual machine, g++4.8.1, libstc++, -O3 -march=native -fwhole-program -ftree-vectorize).

Variable names

void merge(std::vector<int>& a, int p, int q, int r)

As others have mentioned, many people prefer a bit more meaningful variable names. A larger issue I see in these signatures is that they don't tell me whether it's an half-open or closed range.

Const correctness

If you don't intend to modify a variable / parameter, make it const.

Passing containers and offsets

Don't pass containers unless you need to modify the container itself. Using iterators typically leads to better performance, though using pointers might even be faster (my measurements of this algorithm, libstdc++, g++4.8.1).

If we apply those points, but don't change anything related to the algorithm itself:

void merge(int* beg, int* const med, int* const end)
{
    std::vector<int> l(beg, med+1);
    std::vector<int> ri(med+1, end+1);

    int const n1 = med - beg + 1;
    int const n2 = end - med;

    int i, j; i = j = 0;

    while (i < n1 && j < n2) {
        if (l[i] < ri[j]) {
            *beg++ = l[i++];
        } else {
            *beg++ = ri[j++];
        }
    }

    while (i < n1) {
        *beg++ = l[i++];
    }

    while (j < n2) {
        *beg++ = ri[j++];
    }
}

void merge_sort(int* const p, int* const r)
{
    if (p < r) {
        int* const q = p + (r - p) / 2;
        merge_sort(p, q);
        merge_sort(q + 1, r);
        merge(p, q, r);
    }
}

Takes about 330 ms to sort 1E6 integers.

---

Usage of closed ranges

Use half-open ranges if possible. You can more easily express the concept of an empty range as a half-open range [x, x) than with closed ranges.

Two allocations instead of one

You create two temporary vectors, but you only need some temporary storage. A first improvement is to use one vector. It might also be interesting to try std::get_temporary_buffer instead of std::vector.

Stability

While merging, you should use the left element first even if it's equivalent to the right:

        if (l[i] < ri[j]) { // not stable
            *beg++ = l[i++];
        } else {
            *beg++ = ri[j++];
        }

Simply invert this check to ri[j] < l[i] and invert the branches accordingly. This doesn't matter for ints, but I think it's a good habit since it guarantees stability for e.g. classes, where we use only some part of the value for the order relation.

If we apply those points and also change the algorithm to use pointers instead of offsets internally (not just in the interface):

void merge(int* beg, int const* const med, int const* const end)
{
    std::vector<int> l(beg, end);

    int const* cur1 = &l[0];
    int const* cur2 = &l[0] + (med-beg);

    int const* const end1 = cur2;
    int const* const end2 = std::next(&l.back());

    while (cur1 != end1 && cur2 != end2) {
        if (*cur2 < *cur1) {
            *beg++ = *cur2++;
        } else {
            *beg++ = *cur1++;
        }
    }

    while (cur1 != end1) {
        *beg++ = *cur1++;
    }

    while (cur2 != end2) {
        *beg++ = *cur2++;
    }
}

void merge_sort(int* const beg, int* const end)
{
    if (beg != end) {
        int* const med = beg + (end - beg) / 2;
        if(end - med > 1) // check required for half-open ranges
        {
            merge_sort(beg, med);
            merge_sort(med, end);
        }
        merge(beg, med, end);
    }
}

Takes about 270 ms to sort 1E6 integers.

---

We can now templatize the algorithm, but, as I said, using pointers turned out to be faster than using iterators:

template<class RaIt>
void merge(RaIt beg, RaIt med, RaIt end)
{
    using value_type = typename std::iterator_traits<RaIt>::value_type;
    std::vector<value_type> tmp(std::make_move_iterator(beg),
                                std::make_move_iterator(end));

    auto cur1 = &tmp.front();
    auto cur2 = &tmp.front() + (med-beg);

    auto const end1 = cur2;
    auto const end2 = std::next(&tmp.back()); // UB? don't think so..

    while (cur1 != end1 && cur2 != end2) {
        if (*cur2 < *cur1) {
            *beg++ = std::move(*cur2++);
        } else {
            *beg++ = std::move(*cur1++);
        }
    }

    while (cur1 != end1) {
        *beg++ = std::move(*cur1++);
    }

    while (cur2 != end2) {
        *beg++ = std::move(*cur2++);
    }
}

template<class RaIt>
void merge_sort(RaIt beg, RaIt end)
{
    if (beg != end) {
        auto const med = beg + (end - beg) / 2;
        if(end - med > 1)
        {
            merge_sort(beg, med);
            merge_sort(med, end);
        }
        merge(beg, med, end);
    }
}

---

Standard algorithms

Ok, this is probably beside the point, but you can use standard algorithms here:

• std::copy inside the merge algorithm instead of manual loops, or rather std::move (the algorithm on ranges, not the cast)
• std::merge
• std::inplace_merge (215 ms, which tells us that the allocation or the copying still is a bottleneck)
• std::sort (90 ms)

Answer 2

The first thing I would suggest is using better names for your variables. It's very hard for someone else looking at or using your code to determine what those variables are supposed to represent.