Mergesort with a half-sized help vector

Question

I've been trying to optimize a mergesort implementation by using a help vector that is only half the size of the vector that needs to be sorted. It should be possible, but I don't see it. The normal merge uses a full sized help vector, has 2 iterators on the original vector, one starting at the left site and one just at (or past if the vector has an even size) the middle.

Full sized help vector merge

void TDMergeSort<T>::merge(vector<T>& v, int links, int midden, int rechts, vector<T>& hulp) const{
        int j = links;
        int li = links;
        int ri = midden;
        while (li < midden && ri < rechts) {
            if (v[li] < v[ri]) {
                hulp[j++] = v[li++];
            } else {
                hulp[j++] = v[ri++];
            }
        }

        while (li < midden) {
            hulp[j++]=v[li++];
        }
        while (ri < rechts) {
            hulp[j++]=v[ri++];
        }
    for(int i=links;i<rechts;i++){
        v[i]=move(hulp[i]);
    }
}

How can you convert this to a version where hulp is not v.size(), but v.size()/2?

Answer 1

Once I used a similar approach to solve a HackerRank problem (see below for the adaptation to your approach):

void merge(std::vector<int>& original, long long left, long long middle, const long long end) {
    const std::vector<int> leftSide({original.begin()+left, original.begin()+middle});
    const std::vector<int>& rightSide=original; // just to make the code clearer
    auto posForward=left;
    auto right=middle;
    // reset left offsets because we are using a new collection
    middle -= left, left = 0;
    for ( ; left < middle && right < end; ++posForward) {
        if (leftSide[left] <= rightSide[right]) {
            original[posForward] = leftSide[left++];
        } else {
            original[posForward] = rightSide[right++];
            // inversions += (middle-left); // info: removed for this SO answer
        }
    }
    while (left < middle) {
        original[posForward++] = leftSide[left++];
    }
    while (right < end) {
        original[posForward++] = rightSide[right++];
    }
}

You can see a full program here

---

Code adapted to your needs:

void TDMergeSort<T>::merge(vector<T>& v, int links, int midden, int rechts, vector<T>& hulp) const {
    hulp = {v.begin()+links, v.begin()+midden};
    int j = links;
    int ri = midden;
    midden -= links;
    int li = 0;

    while (li < midden && ri < rechts) {        
        if (hulp[li] <= v[ri]) {
            v[j++] = hulp[li++];
        } else {
            v[j++] = v[ri++];
        }
    }

    while (li < midden) {
        v[j++]=hulp[li++];
    }
    while (ri < rechts) {
        v[j++]=v[ri++];
    }
}