Ниже вы найдете MergeSort al go в Java. После «Выход из раздела», как управление снова возвращается к функции «Разделение»? Как значения предыдущей итерации сохраняются в локальной переменной? Несмотря на то, что в коде почти везде были точки останова, я не мог этого понять.
public class MyMergeSort {
public static void main(String[] args) {
int arr[] = {7, 4, 8, 9,5};
int n = arr.length;
MyMergeSort ob = new MyMergeSort();
ob.Partition(arr,0,n-1);
ob.printArray(arr);
}
void Partition(int arr[], int low, int high)
{
System.out.println("Partition low="+low+" high="+high);
if (high <= low)
return;
int mid = (low+high)/2;
Partition(arr, low, mid);
System.out.println("----------------Partition1 done-------------");
Partition(arr, mid+1, high);
System.out.println("----------------Partition2 done----------------");
merge(arr, low, mid, high);
System.out.println("Exit Partition");
printArray(arr);
}
public static void merge(int[] array, int low, int mid, int high)
{
int leftArray[] = new int[mid - low + 1];
int rightArray[] = new int[high - mid];
for (int i = 0; i < leftArray.length; i++)
leftArray[i] = array[low + i];
for (int i = 0; i < rightArray.length; i++)
rightArray[i] = array[mid + i + 1];
int leftIndex = 0;
int rightIndex = 0;
for (int i = low; i < high + 1; i++) {
if (leftIndex < leftArray.length && rightIndex < rightArray.length) {
if (leftArray[leftIndex] < rightArray[rightIndex]) {
array[i] = leftArray[leftIndex];
leftIndex++;
} else {
array[i] = rightArray[rightIndex];
rightIndex++;
}
} else if (leftIndex < leftArray.length) {
// If all elements have been copied from rightArray, copy rest of leftArray
array[i] = leftArray[leftIndex];
leftIndex++;
} else if (rightIndex < rightArray.length) {
// If all elements have been copied from leftArray, copy rest of rightArray
array[i] = rightArray[rightIndex];
rightIndex++;
}
}
System.out.println("merging done");
}
public void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}