Вопрос об алгоритме слияния. После «Выход из раздела», как управление снова возвращается к функции «Разделение»? - PullRequest
0 голосов
/ 01 февраля 2020

Ниже вы найдете 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(); 
     } 
}
...