Merge when merging sort without using temporary arrays

Question

I am trying to implement a merge sort, but somehow got stuck during the day.

[Sorry to insert a lot of code, but I could not do without it]

Implementation:

Merge Sort Function

int mergeSort(int arr[], int low, int high) { int half = (low + high) / 2 ; /* FInd the middle element */ if (low < high) { if (high - low == 1) /* If only one 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; } 

Merge Step - Merge Function

 int merge(int arr[], int low, int half, int high) { int i = 0, j =0, k = 0, l = 0, temp; /* Initialize indices */ for(i = low, j = half;i < half && j < high; i++,j++) /* Swap in the array itself if the elements are out of order */ { if (arr[i] > arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } i = 0,j = low; /* Compare and copy the elements in a global arrray C */ for(k = 0; k < SIZE && i < 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 to the end of the array C */ { for (l = i; l < low; l++) { c[k++] = arr[l]; } } else { for (l = j; l < high; l++) { c[k++] = arr[l]; } } 

Exit

 8 --> 9 --> 4 --> 5 --> 8 --> 9 --> 4 --> 5 --> 8 --> 9 --> 1 --> 2 --> 4 --> 5 --> 8 --> 9 --> /* Sorting when left is sorted but right is in the 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 --> 

Description of the problem

I do not use a local array to store the elements of the array. Instead, the elements are swapped if they are out of order and then copied to the global array by comparison Example: if I have an array

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

Then, firstly, {8,9} will be sorted, and then {4,5} will be sorted, and then, when the copy procedure is copied ie {8,4} and so on. The following recursive calls are available.

 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 and so on. 

When merge is called when {4,5,8,9} sorted and merge(4,5,6) is called on the right, I have the following array

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

So, algo tries to sort {4,5,8,9} and {1,2} when {1,2} not part of this subtask, i.e. I want {1,2} and '{6,7} become {1,2,6,7} , and then combine both of them.

How can I overcome this? I’ve been stuck for so many hours.

thanks a lot