bad_alloc on new

[Sh0es]

I'm getting a bad_alloc error in this section of my code.

int s = l - f;
int half = s/2;
int ind = 0;

string* fst = new string[half]();
string* lst = new string[s-half](); //bad_alloc error thrown 

I really don't have anything else to tell you.

[Disch]

if 'f' is greater than 'l', then 's' will be negative, which will wrap to an insanely high number when sent to new[]. That could be causing the allocation error.

Check to make sure s > 0 before doing this allocation.

[Sh0es]

After inspecting the algorithm in question in debug, I eventually came across the following output.

f = 20, l = 38, s (l - f) = -1849398698. This must be where the bad_alloc is coming from. Can you inspect my code for any possible way this could happen?

string* merge(string* f, string* l, int s)
{
    string* n = new string[s]();

    for(int i = 0; i < s; i += 2)
    {
        if(f[i] > l[i])
        {
            n[i] = l[i];
            n[i+1] = f[i];
        }
        else
        {
            n[i] = f[i];
            n[i+1] = l[i];
        }
    }

    return n;
}
string* mgsort(string* c, int f, int l)
{
    int s = l - f;
    int half = s/2;
    int ind = 0;

    string* fst = new string[half]();
    string* lst = new string[s-half]();

    while(ind < half)
    {
        fst[ind] = c[ind];
        ++ind;
    }
    while(ind < s)
    {
        lst[ind-half] = c[ind];
        ++ind;
    }

    delete[] c;
    return merge(mgsort(fst, 0, half), mgsort(lst, half+1, s), s);
}
void msort(string* c, int l)
{
    int half = l/2;
    int ind = 0;

    string* fst = new string[half]();
    string* lst = new string[l-half]();

    while(ind < half)
    {
        fst[ind] = c[ind];
        ++ind;
    }
    while(ind < l)
    {
        lst[ind-half] = c[ind];
        ++ind;
    }

    delete[] c;
    c = merge(mgsort(fst, 0, half), mgsort(lst, half+1, l), l);

    delete[] fst;
    delete[] lst;
}