Error on memory allocation in c++

Question

I am writing code for bottom-up merge sort in c++, but this error occurs on a line where I am allocating memory to a pointer,

void merge(int *a, int low, int high, int mid,int max)
{
   int i, j, k; 
   int *c=new int[max];   //error occurs here
   i = low;
   k = low;
   j = mid + 1;
   while (i <= mid && j <= high)
   {
       if (a[i] < a[j])
       {
           c[k] = a[i];
           k++;
           i++;
       }
       else
       {
           c[k] = a[j];
           k++;
           j++;

       }
   }
   while (i <= mid)
   {
       c[k] = a[i];

       k++;
       i++;
   }
   while (j <= high)
   {
       c[k] = a[j];
       k++;
       j++;
   }
   for (i = low; i < k; i++)
   {
       a[i] = c[i];
   }
}

What is the problem, looks like no more memory available??

Answer 1

Your corruption problem is this:

k = low;

You're using k as the index into your temporary array. It should start at 0, not low Change it to:

k = 0;

Regarding the rest of your algorithm, you have a blatant memory leak. You're not deleting your temporary array. Also, the algorithm of merge sort is considerably easier in C and C++ than most languages precisely because of its native ability with pointer arithmetic

For example:

template<typename T>
void merge(T* ar, size_t mid, size_t len)
{
    T *merged = new T[len]; // note. normally i would use a smart pointer

    size_t i=0, j=mid, k=0;
    while (i<mid && j<len)
    {
        if (ar[i] < ar[j])
            merged[k++] = ar[i++];
        else
            merged[k++] = ar[j++];
    }

    while (i < mid)
        merged[k++] = ar[i++];
    while (j < len)
        merged[k++] = ar[j++];

    std::copy(merged, merged+k, ar);
    delete [] merged;
}

template<typename T>
void mergesort(T* ar, size_t len)
{
    if (len<2)
        return;

    mergesort(ar, len/2);
    mergesort(ar+len/2, len-len/2);
    merge(ar, len/2, len);
}

Using the above. the following demonstrates how it is called:

int main()
{
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<> dist(1,99);

    std::vector<int> data;
    data.reserve(25);
    std::generate_n(std::back_inserter(data), data.capacity(),
                    [&](){ return dist(rng);});

    for (auto x : data)
        std::cout << x << ' ';
    std::cout << '\n';

    mergesort(data.data(), data.size());

    for (auto x : data)
        std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output (obviously varies)

55 39 40 87 49 1 94 8 20 47 42 23 93 99 81 52 17 66 3 6 74 5 49 13 67 
1 3 5 6 8 13 17 20 23 39 40 42 47 49 49 52 55 66 67 74 81 87 93 94 99 

All of that said, unless this is for academia you're crazy not to just use std::sort

---

Alternative Allocation

The bottom-up design works well in different cases, but the memory allocation system it utilizes is dreadful for large sets. The total temp space needed will never be more than N items for an N-item container, so you can allocated it up-front with a front-loader to the actual merge sort that is then, along with the merge algorithm, provided temp space to use rather than allocating their own. The only tricky part is knowing where in the tmp storage it is safe to use space. But you already know that. The same offsets you're using for your sequence being sorted can also be used for the proper matching temp-space locations:

template<typename T>
void merge(T* ar, size_t mid, size_t len, T* tmp)
{
    size_t i=0, j=mid, k=0;
    while (i<mid && j<len)
    {
        if (ar[i] < ar[j])
            tmp[k++] = ar[i++];
        else
            tmp[k++] = ar[j++];
    }

    while (i < mid)
        tmp[k++] = ar[i++];
    while (j < len)
        tmp[k++] = ar[j++];

    std::copy(tmp, tmp+k, ar);
}


template<typename T>
void mergesort_int(T* ar, size_t len, T* tmp)
{
    if (len < 2)
        return;

    mergesort_int(ar, len/2, tmp);
    mergesort_int(ar+len/2, len-len/2, tmp+len/2);
    merge(ar, len/2, len, tmp);
}

template<typename T>
void mergesort(T* ar, size_t len)
{
    if (len<2)
        return;

    std::vector<T> tmp(len)
    mergesort_int(ar, len, &tmp[0]);
}

Using the same main() from the previous sample, the outcome is similar:

24 9 26 93 35 75 99 95 49 58 32 37 30 88 55 13 76 23 99 90 50 66 38 8 3 
3 8 9 13 23 24 26 30 32 35 37 38 49 50 55 58 66 75 76 88 90 93 95 99 99 

Remember, this now requires one single allocation N items (in our case we use a vector for the automatic memory management) which is then used throughout the algorithm. You will find this is considerably faster, particularly for large sets of data.