c - Merging in merge sort without using temporary arrays -

i'm trying implement merge sort somehow have been stuck day.

[sorry pasting big amount of code wouldn't able without it]

implementation:

merge sort - function

int mergesort(int arr[], int low, int high) {         int half = (low + high) / 2 ;    /* find middle element */          if (low < high)         {             if (high - low == 1)             /* if 1 element, return */                 return;             mergesort(arr,low,half);    /* sort first half */             mergesort(arr,half, high); /* sort second half */             merge(arr,low,half,high);  /* merge */         }       return success; } 

merging step - merge function

int merge(int arr[], int low, int half, int high) {     int = 0, j =0, k = 0, l = 0, temp;    /* initialize indices */      for(i = low, j = half;i < half && j < high; i++,j++)    /* swap in array if elements out of order */     {         if (arr[i] > arr[j])         {             temp = arr[i];             arr[i] = arr[j];             arr[j] = temp;         }      }      = 0,j = low;  /* compare , copy elements in global arrray c */     for(k = 0; k < size && < low && j < high; k++)     {         if (arr[i] < arr[j])         {             c[k] = arr[i];             i++;         }         else         {             c[k] = arr[j];             j++;         }     }      if (i < j) /* copy remaining elements end of array c */     {         (l = i; l < low; l++)         {             c[k++] = arr[l];         }     }     else     {         (l = j; l < high; l++)         {             c[k++] = arr[l];         }     } 

output

8 --> 9 -->  4 --> 5 --> 8 --> 9 -->  4 --> 5 --> 8 --> 9 -->  1 --> 2 --> 4 --> 5 --> 8 --> 9 --> /* sorting when left sorted right in process ? */ 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 1 --> 2 -->  1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 -->  1 --> 2 --> 6 --> 7 --> 4 --> 5 --> 8 --> 9 -->  

problem description

i'm not using local array storing elements of array. instead elements swapped if out of order , copied global array comparison example: if have array

{ 9, 8, 4, 5, 2, 1, 7, 6} 

then, firstly {8,9} sorted , {4,5} sorted , when copying procedure i.e {8,4} compared , on. following recursive calls take place

mergesort(0,8) -> mergesort(0,4) , mergesort(4,8), merge(0,4,8) mergesort(0,4) -> mergesort(0,2) , mergesort(2,4), merge(0,2,4) mergesort(0,2) -> 1 element calls , on. 

when merge called when {4,5,8,9} sorted , , right called merge(4,5,6) have following array

{4,5,8,9,1,2,7,6} 

so, algo tries sort {4,5,8,9} , {1,2} when {1,2} not part of subproblem i.e want {1,2} , '{6,7} become {1,2,6,7} , combine both of these.

how overcome this? have been stuck many hours.

thanks lot