patterncppMinor

Mergesort with std::vector

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

withstdvectormergesort

Problem

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

using size = std::size_t;

template
void merge(std::vector& v, size low, size mid, size high) {
    size i = low, j = mid+1;
    std::vector old{v};
    for (size x = low; x  mid) {
            v[x] = old[j++];
        } else if (j > high){
            v[x] = old[i++];
        } else if (old[j] 
void sort(std::vector& v, size low, size high) {
    if (high 
void sort(std::vector& v) {
    if (v.size() < 2) {
        throw std::out_of_range("out of range");
    }
    sort(v,0,v.size()-1);
}

Solution

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 operator5, 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  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

 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
void merge(I low, I mid, I high) {
    I i   = low;
    I j   = mid;

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

    while(i 
// requires std::RandomAccessIterator           // Proposed C++17 syntax for concepts.
//       && std::LessThanComparable>
void sort(I low, I high) {
    size size = std::distance(low, high);
    if(size 
void sort(C& v) {
    sort(std::begin(v), std::end(v));
}

Code Snippets

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

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

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

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

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

Context

StackExchange Code Review Q#74410, answer score: 7

Revisions (0)

No revisions yet.