Below merge sort is a good implementation? I did not want to create temp arrays for merging. I just wanted to merge inline.
Can you provide any additional feedback to consider?
// sort(arr,0, arr.length - 1);
void sort(int[] arr, int left, int right){
if(right - left < 1)
return;
int mid = (left + (right - left) / 2);
sort(arr, left, mid);
sort(arr,mid + 1, right);
merge(arr, left, mid, right);
}
void merge(int[] arr, int left, int mid, int right){
int j = mid + 1;
for (int i = left; i <= mid; i++) {
j = mid + 1;
if(arr[i] > arr[j]){ // compare left array with right array first element
swap(arr, i, j);
while(j < right && arr[j] > arr[j + 1]){
swap(arr, j, j + 1);
j++;
}
}
}
}
void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}