Mergesort with std::vector

Question

I made a mergesort implementation based on this code. Please review my C++ version.

using size = std::size_t;

template<typename T>
void merge(std::vector<T>& v, size low, size mid, size high) {
    size i = low, j = mid+1;
    std::vector<T> old{v};
    for (size x = low; x <= high; ++x) {
        if (i > mid) {
            v[x] = old[j++];
        } else if (j > high){
            v[x] = old[i++];
        } else if (old[j] < old[i]) {
            v[x] = old[j++];
        } else {
            v[x] = old[i++];
        }
    }
}

template<typename T>
void sort(std::vector<T>& v, size low, size high) {
    if (high <= low) {
        return;
    }
    size mid = (high+low)/2;
    sort(v,0,mid);
    sort(v,mid+1,high);
    merge(v,low,mid,high);
}

template<typename T>
void sort(std::vector<T>& v) {
    if (v.size() < 2) {
        throw std::out_of_range("out of range");
    }
    sort(v,0,v.size()-1);
}

Answer 1

You have decided your ranges are inclusive:

sort(v,0,v.size()-1);

So low=>lowest member, high=>highest member.
Most C++ code uses the one past the end system (see iterators). Not a huge deal. It just means you need to use operator<= rather than operator< and you have to sprinkle a couple of +1 around.

Your main merge loop is easier to write if you concentrate on what it is supposed to do (Compare items from the two ranges).

while(i <= mid && j <= high) {
    if (old[j] < old[i]) {
        v[x++] = old[j++];
    } else {
        v[x++] = old[i++];
    }
}

At this point one of the ranges is exhausted, so all the elements must come from the other range. So just copy them.

while(i <= mid) {
   v[x++] = old[i++];
}
while(j <= high) {
   v[x++] = old[j++];
}

But we can also replace manual loops using algorithms:

std::copy(&old[i], &old[mid+1],  &v[x]); x+= (mid-i)+1;
std::copy(&old[j], &old[high+1], &v[x]);

Also, you are copying the whole array into old when you are only going to alter a subset of it. Say the vector contains 10,000 elements. But this merge you are merging low=>5, mid=>6, high=>7 that seems like a lot of extra copying.

I would simplify this and sort into an external array, then copy only the sorted elements back.

std::vector<T>  sorted(high-low+1);
while(i <= mid && j <= high) {
    if (old[j] < old[i]) {
        sorted[x++] = v[j++];
    } else {
        sorted[x++] = v[i++];
    }
}
std::copy(&v[i], &v[mid+1],  &sorted[x]); x+= (mid-i)+1;
std::copy(&v[j], &v[high+1], &sorted[x]);

std::copy(sorted.begin(), sorted.end(), &v[low]);

Since we are in the era of C++14, we can do a lot better than copying the array. We can introduce the concept of a move and move the elements around. For integers there is no difference, but if T is a big object, we would rather move it if we can.

        sorted[x++] = v[j++];

        // becomes.

        sorted[x++] = std::move(v[j++]);

Rather than passing the index and the container, just pass iterators (now it becomes easier to use the one past the end metaphor). Also, we can generalize the container to a C so that you can pass any container.

The result is:

template<typename I>
void merge(I low, I mid, I high) {
    I i   = low;
    I j   = mid;

    typedef typename I::value_type  value_type;
    std::vector<value_type> sorted(std::distance(low, high));
    auto x = sorted.begin();

    while(i < mid && j < high) {
        if (*j < *i) {
            // Use move semantics. So we don't copy expensive T object around.
            (*x) = std::move(*j); ++j;++x;
        }
        else {
            // Put the ++ inline to show difference in readability.
            // Prefer the above to this.
            (*x++) = std::move(*i++);
        }
    }
    // Don't use a manual loop when you can use an already optimized algorithm
    x = std::move(i, mid,  x);
    x = std::move(j, high, x);

    // Now move the sorted values back.
    std::move(std::begin(sorted), std::end(sorted), low);
}

template<typename I>
// requires std::RandomAccessIterator<I>           // Proposed C++17 syntax for concepts.
//       && std::LessThanComparable<typename I::value_type>>
void sort(I low, I high) {
    size size = std::distance(low, high);
    if(size <= 1) {
        return;
    }
    I    mid(low)
    std::advance(mid, size/2);
    sort(low, mid);
    sort(mid, high);
    merge(low, mid, high);
}

template<typename C>
void sort(C& v) {
    sort(std::begin(v), std::end(v));
}

Answer 2

sort(v,0,mid);

This is incorrect. You are constantly resorting the bottom of the array. Assuming it works, it will ruin the time complexity. You will actually be sorting the exact same array segment multiple times.

sort(v, low, mid);

This just sorts half the section that the function was asked to sort.

if (v.size() < 2) {
    throw std::out_of_range("out of range");
}

First, this introduces a magic number. What's special about 2? The answer is that it is one more than 1.

if (v.size() <= 1) {
    throw std::out_of_range("out of range");
}

This more directly shows what is important. However, why describe it that way? Why is sorting a single element or empty vector "out of range"? More normally, we'd just describe these as already sorted.

if ( v.size() <= 1 ) {
    return;
}

We could even reduce this further, as we only need to check <= 0 or < 1, but adding 1 costs us nothing and saves us a function call if it equals 1. The only reason we need it at all is that std::size_t is an unsigned type, so subtracting from zero will have odd results.

This also avoids the oddity of passing a perfectly valid vector to the function only to be told that something is "out of range".