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