Блог

Я просматривал приведенный ниже пример программы и пытался понять, как работает приведенная ниже рекурсия, я не мог понять, как сортируются левые и правые элементы массива, и, наконец, слияние двух подмассивов, как показано ниже. Любое наглядное объяснение приведенного ниже метода было бы очень полезным, поскольку я пытаюсь понять приведенный ниже рекурсивный код.

  public static int[] mergeSort(int[] arrayToSort) {

    // BASE CASE: arrays with fewer than 2 elements are sorted
    if (arrayToSort.length < 2) {
        return arrayToSort;
    }

    // STEP 1: divide the array in half
    // we use integer division, so we'll never get a "half index"
    int midIndex = arrayToSort.length / 2;

    int[] left  = Arrays.copyOfRange(arrayToSort, 0, midIndex);
    int[] right = Arrays.copyOfRange(arrayToSort, midIndex, arrayToSort.length);

    // STEP 2: sort each half
    int[] sortedLeft  = mergeSort(left);
    int[] sortedRight = mergeSort(right);

    // STEP 3: merge the sorted halves
    int[] sortedArray = new int[arrayToSort.length];

    int currentLeftIndex  = 0;
    int currentRightIndex = 0;

    for (int currentSortedIndex = 0; currentSortedIndex < arrayToSort.length;
            currentSortedIndex  ) {

        // sortedLeft's first element comes next
        // if it's less than sortedRight's first
        // element or if sortedRight is exhausted
        if (currentLeftIndex < sortedLeft.length
                amp;amp; (currentRightIndex >= sortedRight.length
                || sortedLeft[currentLeftIndex] < sortedRight[currentRightIndex])) {
            sortedArray[currentSortedIndex] = sortedLeft[currentLeftIndex];
            currentLeftIndex  ;
        } else {
            sortedArray[currentSortedIndex] = sortedRight[currentRightIndex];
            currentRightIndex  ;
        }
    }

    return sortedArray;
}
 

Сортировка выполняется в цикле слияния:

• если массив очень маленький (0 или 1 элемент), mergeSort() возвращает его немедленно.
• в противном случае он разбивает массив на 2 подмассива примерно одинакового размера, left и right , которые сортируются путем рекурсивного вызова одного и того же метода:

     // STEP 2: sort each half
    int[] sortedLeft  = mergeSort(left);
    int[] sortedRight = mergeSort(right);
   

• на последнем шаге выполняется итерация по отсортированным половинкам для создания нового отсортированного массива.

Рекурсивные вызовы завершаются, потому что они выполняются только с подмассивами, строго меньшими, чем массив аргументов.