C++ recursive string mergesort

Question

This is a homework question so while I'd like usable code what I'm really seeking is insight on how to tackle this problem. I have two sorted arrays in ascending order that I need to combine in a recursive function. It seems like I need to institute the sorting part of a merge sort algorithm. The requirements are that the recursive function can only take the two sorted strings as parameters and it cannot use global or static variables.

I think the psuedocode is:

• if the size of the two strings == 0 then return the result string.
• compare substr(0,1) of each strings to see which is lesser, and append that to result string
• recursively call the function with the new parameters being a substr of the string that appended

My questions are: how do I save a result string if I can't use static variables? I've seen code where a string is defined as = to the return statement of the recursive call. Would that work in this case?

The second question is how to increment the function. I need to call a substr(1,size-1) after the first iteration and then increment that without using static variables.

Here's my attempt to solve the equation WITH static variables (which are not allowed):

static string result="";
static int vv=0;
static int ww=0;

if(v.size()==0 && w.size()==0)
    return result;
if(w.size()==0 || v.substr(0,1) <= w.substr(0,1)){ 
    result+=v.substr(0,1);
    vv++;
    return spliceSortedStrings( v.substr(vv,v.size()-vv) , w); 
    }
else if(v.size()==0 || w.substr(0,1) > v.substr(0,1)){
    result+=w.substr(0,1);
    ww++;
    return spliceSortedStrings( v , w.substr(ww,w.size()-ww));
    }

I'll be appreciative for any guidance.

Answer 1

How about this:

std::string merge(std::string a, std::string b) {
    if (a.size() == 0) return b;
    if (b.size() == 0) return a;

    if (a.back() < b.back()) {
        std::string m = merge(a, b.substr(0, b.size()-1));
        return m + b.back();
    }
    else {
        std::string m = merge(a.substr(0, a.size()-1), b);
        return m + a.back();
    }
}

Correctness and termination should be obvious, and I think it should fit the constraints you are given. But I wonder what teacher would pose such a task in C++, for the above code is about as inefficient as it possibly can be.