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::mergestd::inplace_merge (215 ms, which tells us that the allocation or the copying still is a bottleneck)std::sort (90 ms)
