Как работает этот алгоритм слияния (mergeSort)?

Question

[Den4_x]

public static void mergeSort(int[] array, int low, int high) {
        if (high - low < 2) {
            return;
        }
        int mid = (low + high) >>> 1;
        mergeSort(array, low, mid);
        mergeSort(array, mid, high);
        int[] b = Arrays.copyOfRange(array, low, mid);
        for (int i = low, j = mid, k = 0; k < b.length; i++) {
            if (j == high || b[k] <= array[j]) {
                array[i] = b[k++];
            } else {
                array[i] = array[j++];
            }
        }
    }

Я понимаю, как он работает визуально, но на коде, мне очень трудно здесь сориентироваться. Объясните подробно, что и как тут работает.

Comments

[longclaps]

Дружище, неясно как помочь тебе. Сделай вот что: к каждой строке этого кода припиши свой комментарий: что она делает, или напиши "не понимаю". Это должно помочь.

[Den4_x]

longclaps, начиная с цикла становится как-то всё непонятно для меня.

[longclaps]

объясните подробно пожалуйста
к каждой строке этого кода припиши свой комментарий
начиная с цикла становится как-то всё непонятно для меня

Den4_x, так не пойдёт: ты хочешь подробных разъяснений, но как я пойму, что строки до цикла ты трактуешь правильно?

[Den4_x]

class MergeSort {

    public static void mergeSort(int[] array, int low, int high) {//low - 1-ый индекс эл-та в массиве, high -  кол-во эл-ов в массиве
        if (high - low < 2) {//  (0 - кол-во эл-ов массива) в итоге остается кол-во эл-ов в массиве и выполняется проверка, если 1 эл-нт, то функция завершается
            return;
        }

        int mid = (low + high) >>> 1;//деление на 2 то есть кол-во эл-ов делим на 2 и узнаем чему равна половина массива (в коол-ве эл-ов)

        mergeSort(array, low, mid);//понял, что это рекурся, но не понимаю,
        //как это взаимодейсвует с кодом далее или  такго взаимодействия нет + я так думаю, что это разбиение как раз таки массива на мелкие части
        mergeSort(array, mid, high);//строка выше

        int[] b = Arrays.copyOfRange(array, low, mid);//загружаем основную левую половину массива, но потом не оганяю, как туда загружаются еще и другие части или нет

        for (int i = low, j = mid, k = 0; k < b.length; i++) {//вроде как мы обращаемся ко всем индексам массива который зодержит все эл-ты половины основного массива,
            //но не шарю зачюм здесь обьявлют еще i = low, j = mid
            if (j == high || b[k] <= array[j]) {//тут не понимаю,  что значят эти проверки j == high || b[k] <= array[j]
                
                array[i] = b[k++]; // и н могу предствить это визуально, что это
            } else {
                array[i] = array[j++];// и н могу предствить это визуально, что это
            }
        }

    }

}

сори за опчечатки, если что)

[longclaps]

Den4_x, смотри

[longclaps]

Den4_x,

class MergeSort {

    public static void mergeSort(int[] array, int low, int high) {
        if (high - low < 2) {//  (0 - кол-во эл-ов массива) в итоге остается кол-во эл-ов в массиве и выполняется проверка, если 1 эл-нт или 0, то функция завершается
            return;
        }

        int mid = (low + high) >>> 1;//low - нижняя граница куска массива, который будем сортировать, high - верхняя граница,  mid - индекс середины
    
        mergeSort(array, low, mid);// сортируем кусок между low и mid
        mergeSort(array, mid, high);// сортируем кусок между mid и high

        int[] b = Arrays.copyOfRange(array, low, mid);//копируем левую (нижнюю) половину массива в переменную b
        
// смотри, у нас два источника, которые будем сливать - b и правый кусок (между mid и high)
// а приёмником будет весь кусок от low до high
        
        for (int i = low, j = mid, k = 0; k < b.length; i++) {
            // i = low - стартовая позиция приёмника, j = mid - стартовая позиция в куске от mid до high
            // k = 0 - стартовая позиция в b
            if (j == high || b[k] <= array[j]) {//j == high - кончились числа в правом подмассиве или b[k] <= array[j] текущее число из b <= текущее число из правой половины
                
                array[i] = b[k++]; // пихаем число из b
            } else {
                array[i] = array[j++];// пихаем число из правой половины
            }
        }

    }

}

[Денис Загаевский]

Den4_x, гуглить "рекурсия", "постинкремент", "сравнение".
И кури синтаксис джавы, "визуально представлять" девок будешь, а здесь понимать каждый символ надо.

[Den4_x]

longclaps, Спасибо огромное, а low и high тут в качестве индексов(граница массива) или нет?

Answer 1

[Александр Скуснов]

Пункт 2 немецкий танец
https://forany.xyz/a-370