Merge Sort with dynamic arrays

[JADM]

Hello Everybody, i am trying to make a program in c++ which uses the merge sort algorithm, my code compiles properly but it work's just for some cases, in fact i have discovered that it works when pair array's positions are greater that odd positions, my array is generated dynamically and with random values. I hope somebody could help me a little i will apreciate it, thanks in advance.

This is my Code (i'm using Code::Blocks)

#include <cstdlib>
#include <cstdio>
#include <ctime>

void print(int *list, int size){ //this function prints an array

for (int i = 0; i < size; i++){

printf("%5i", list[i]);
}
printf("\n\n");
}

int *merge(int *a, int n, int *b, int m){

int *c = new int [n+m];
int i = 0, j = 0, k = 0;
while(i <= n && j <= m){

if (a[i] < b[j]){

c[k] = a[i];
i++;
}
else {

c[k] = b[j];
j++;
}
k++;
}
while (i < n){

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

c[k] = b[j];
j++;
k++;
}
return c;
}

void msort(int *&list, int n){

if (n > 1){

int k = n / 2;
int l = n % 2;
int *a1 = new int [k];
for (int i = 0; i < k; i++){ a1[i] = list[i]; }

int *a2 = new int [k+l];
for (int i = k, j = 0; i < n; i++, j++){ a2[j] = list[i]; }

msort(a1, k);
msort(a2, k+l);
list = merge(a1, k, a2, k+l);
delete a1;
delete a2;
}
}

int main (){

srand(time(NULL));

int size = 10;
int *list = new int [size];
for (int i = 0; i < size; i++) { list[i] = rand() %100 + 1; }

print(list, size);

msort(list, size);

print(list, size);

return 0;
}

[cire]

Ignoring for a moment that you're leaking memory like a sieve, let's take a look at the following function:

int *merge(int *a, int n, int *b, int m)
{
    int *c = new int[n + m];
    int i = 0, j = 0, k = 0;

    while (i <= n && j <= m)
    {
        if (a[i] < b[j])
        {
            c[k] = a[i];
            i++;
        }
        else
        {
            c[k] = b[j];
            j++;
        }
        k++;
    }

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

    while (j < m)
    {
        c[k] = b[j];
        j++;
        k++;
    }

    return c;
}

One truism when working with C-style arrays is that valid indices into an array are 0 to size-1 where size is the number of elements in the array. With that in mind, take another look at the loop condition on line 6. The loop continues to execute while both i and j are less than or equal to n and m which are the respective number of elements in a and b. Since a and b are being indexed by i and j this means that both indexes have the potential to be out of the range of the array which they are meant to index. Don't access outside the boundaries of arrays - it always leads to bad things happening at some point.

merge should not create a new array. It should store the result in an already existing area of memory.

You should also keep in mind that merge sort is typically used for linked lists, not arrays.

[ Edit: new should be paired with delete. new[] should be paired with delete[]. ]