IAMTubby

October 20th, 2014, 04:49 PM

Hello,

I've been trying to understand this particular part of merge sort for few days, and finally think that I need some advice.

As mentioned in the comments below, merge(A1, n1, A2, n2, A); combines sorted arrays A1 and A2 into A. I understand merge sort well, but I'm not able to understand how the combined sorted array A copies it's values to A1 or A2 depending on who called it when it goes back to the previous invocation of the recursive function.

Let me explain with an example, Say the initial array was : {3,1,2,6,4,7,5,8}

At some step :

A1 : {1,3},

A2 : {2,6}

now call merge(A1,A2,A). This will give

A : {1,2,3,6}

So far so good, but now when it goes back to the previous invocation after doing the two frees,

A1 : {1,2,3,6}

A2 : {4,7,5,8}

How does A1 get these values? I'm confused because, I feel A has already copied it's values to A1 and A2 before calling merge, which means, any changes in A will not be reflected in A1 and A2?

I would like to understand how, A1 in (i-1)th recursive invocation, gets the values in A in the ith invocation

I think it's something to do with merge_sort(int *A, int n) or something, but please can you elaborate a bit further.

int merge_sort(int *A, int n)

{

int i;

int *A1, *A2;

int n1, n2;

if (n < 2)

return; /* the array is sorted when n=1.*/

/* divide A into two array A1 and A2 */

n1 = n / 2; /* the number of elements in A1 */

n2 = n - n1; /* the number of elements in A2 */

A1 = (int*)malloc(sizeof(int) * n1);

A2 = (int*)malloc(sizeof(int) * n2);

/* move the first n/2 elements to A1 */

for (i =0; i < n1; i++) {

A1[i] = A[i];

}

/* move the rest to A2 */

for (i = 0; i < n2; i++) {

A2[i] = A[i+n1];

}

/* recursive call */

merge_sort(A1, n1);

merge_sort(A2, n2);

/* conquer */

merge(A1, n1, A2, n2, A); //assume this function merges the two sorted arrays A1 and A2 into A

free(A1);

free(A2);

}

PS : I have also attached the entire code in case this code snippet is not sufficient.

I've been trying to understand this particular part of merge sort for few days, and finally think that I need some advice.

As mentioned in the comments below, merge(A1, n1, A2, n2, A); combines sorted arrays A1 and A2 into A. I understand merge sort well, but I'm not able to understand how the combined sorted array A copies it's values to A1 or A2 depending on who called it when it goes back to the previous invocation of the recursive function.

Let me explain with an example, Say the initial array was : {3,1,2,6,4,7,5,8}

At some step :

A1 : {1,3},

A2 : {2,6}

now call merge(A1,A2,A). This will give

A : {1,2,3,6}

So far so good, but now when it goes back to the previous invocation after doing the two frees,

A1 : {1,2,3,6}

A2 : {4,7,5,8}

How does A1 get these values? I'm confused because, I feel A has already copied it's values to A1 and A2 before calling merge, which means, any changes in A will not be reflected in A1 and A2?

I would like to understand how, A1 in (i-1)th recursive invocation, gets the values in A in the ith invocation

I think it's something to do with merge_sort(int *A, int n) or something, but please can you elaborate a bit further.

int merge_sort(int *A, int n)

{

int i;

int *A1, *A2;

int n1, n2;

if (n < 2)

return; /* the array is sorted when n=1.*/

/* divide A into two array A1 and A2 */

n1 = n / 2; /* the number of elements in A1 */

n2 = n - n1; /* the number of elements in A2 */

A1 = (int*)malloc(sizeof(int) * n1);

A2 = (int*)malloc(sizeof(int) * n2);

/* move the first n/2 elements to A1 */

for (i =0; i < n1; i++) {

A1[i] = A[i];

}

/* move the rest to A2 */

for (i = 0; i < n2; i++) {

A2[i] = A[i+n1];

}

/* recursive call */

merge_sort(A1, n1);

merge_sort(A2, n2);

/* conquer */

merge(A1, n1, A2, n2, A); //assume this function merges the two sorted arrays A1 and A2 into A

free(A1);

free(A2);

}

PS : I have also attached the entire code in case this code snippet is not sufficient.