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