algorithm - Trouble understanding a specific C implementation of Merge Sort -

i'm trying follow code step step still can't understand steps it's taking.

void merge (int *a, int n, int m) {     int i, j, k;     int *x = malloc(n * sizeof (int));     (i = 0, j = m, k = 0; k < n; k++) {         x[k] = j == n      ? a[i++]              : == m      ? a[j++]              : a[j] < a[i] ? a[j++]              :               a[i++];     }     (i = 0; < n; i++) {         a[i] = x[i];     }     free(x); }  void merge_sort (int *a, int n) {     if (n < 2)         return;     int m = n / 2;     merge_sort(a, m);     merge_sort(a + m, n - m);     merge(a, n, m); } 

here's simple example can see issues are. it's sorting integer array {4,3,2,1} .

#include <stdio.h> #include <stdlib.h>  void merge (int *a, int n, int m) {     int i, j, k;     int *x = malloc(n * sizeof (int));     (i = 0, j = m, k = 0; k < n; k++) {         x[k] = j == n      ? a[i++]              : == m      ? a[j++]              : a[j] < a[i] ? a[j++]              :               a[i++];     }     (i = 0; < n; i++) {         a[i] = x[i];     }     free(x); }  void merge_sort (int *a, int n) {     if (n < 2)         return;     int m = n / 2;     int g;     printf("a before merge_sort(a,m) %i\n",a);     printf("m %i\n",m);     printf("n %i\n",n);     printf("\n");     for(g=0;g<m;++g) printf("%i\n", a[g]);     merge_sort(a, m);     printf("a after merge_sort(a,m) %i\n",a);     printf("m %i\n",m);     printf("n %i\n",n);     printf("\n");     for(g=0;g<m;++g) printf("%i\n", a[g]);     merge_sort(a + m, n - m);     printf("a after merge_sort(a+m, n-m) %i\n",a);     printf("m %i\n",m);     printf("n %i\n",n);     printf("\n");     for(g=0;g<m;++g) printf("%i\n",a[g]);     merge(a, n, m);     printf("a after merge(a,n,m) %i\n ",a);     printf("m %i\n",m);     printf("n %i\n",n);     for(g=0;g<m;++g) printf("%i\n",a[g]); }  int main(){     int test[4] = {4,3,2,1};     int i;     merge_sort(&test[0],4);     printf("\nfinal result:\n");     for(i=0;i<4;++i){         printf("%i ",test[i]);     }     printf("\n"); } 

and here's output.

begin of if end of if(no return)  before merge_sort(a,m) 0xbfadcebc m 2 n 4  4 3  begin of if end of if(no return)  before merge_sort(a,m) 0xbfadcebc m 1 n 2  4  begin of if  after merge_sort(a,m) 0xbfadcebc m 1 n 2  4  begin of if  after merge_sort(a+m, n-m) 0xbfadcebc m 1 n 2  4  after merge(a,n,m) 0xbfadcebc  m 1 n 2  3  after merge_sort(a,m) 0xbfadcebc m 2 n 4  3 4  begin of if end of if(no return)  before merge_sort(a,m) 0xbfadcec4 m 1 n 2  2  begin of if  after merge_sort(a,m) 0xbfadcec4 m 1 n 2  2  begin of if  after merge_sort(a+m, n-m) 0xbfadcec4 m 1 n 2  2  after merge(a,n,m) 0xbfadcec4  m 1 n 2  1  after merge_sort(a+m, n-m) 0xbfadcebc m 2 n 4  3 4  after merge(a,n,m) 0xbfadcebc  m 2 n 4  1 2  final result: 1 2 3 4  

this what's puzzling me:

begin of if  after merge_sort(a+m, n-m) 0xbfadcebc m 1 n 2  4  after merge(a,n,m) 0xbfadcebc  m 1 n 2  3 

i'd expect a+m change address of 0xbfadcebc else, produces number 4 output again. it's if merge(a+m,n-m) didn't have effect , produced same if had written merge(a,n-m).

furthermore, merge(a,n,m) not recursive function, i'd expect function end after running it. don't how this:

a after merge_sort(a,m) 0xbfadcebc m 2 n 4  3 4 

...can next step after merge(a,n,m).

commented code:

/* = ptr sub-array */ /* 0 = starting index */ /* m = mid point index */ /* n = ending index */ /* left  half indices = 0 m-1 */ /* right half indices = m n   */ void merge (int *a, int n, int m) {     int i, j, k;     int *x = malloc(n * sizeof (int)); /* allocate temp array */     (i = 0, j = m, k = 0; k < n; k++) {         x[k] = j == n      ? a[i++]    /* if end of right, copy left */              : == m      ? a[j++]    /* if end of left, copy right */              : a[j] < a[i] ? a[j++]    /* if right < left, copy right */              :               a[i++];   /* else (left <= right), copy left */     }     (i = 0; < n; i++) {          /* copy x[] a[] */         a[i] = x[i];     }     free(x);                           /* free temp array */ }  /* = ptr sub-array */ /* n = size == ending index of sub-array */      void merge_sort (int *a, int n) {     if (n < 2)                         /* if < 2 elements nothing */         return;     int m = n / 2;                     /* m = mid point index */     merge_sort(a, m);                  /* sort a[0] a[m-1] */     merge_sort(a + m, n - m);          /* sort a[m] a[n-1] */     merge(a, n, m);                    /* merge 2 halves */ }