Понимание части сортировки Java сортировка слиянием - PullRequest
Новая
       6

Понимание части сортировки Java сортировка слиянием

0 голосов
/ 07 февраля 2020

Я понимаю, как работает часть слияния сортировки слиянием, однако по какой-то причине я просто не могу обернуть голову вокруг рекурсивной / разделяющей части, которая происходит до вызова функции слияния. Используя приведенный ниже пример кода, я попытался отследить значение различных переменных, но не смог полностью понять, что происходит. 

public void sort(int arr[], int l, int r) { 
    if (l < r) 
    { 
        // Find the middle point 
        int m = (l+r)/2; 

        // Sort first and second halves 
        sort(arr, l, m); 
        sort(arr , m+1, r); 

        // Merge the sorted halves 
        merge(arr, l, m, r); 
    }

}

Мне кажется, что m продолжает передаваться в сортировку до тех пор, пока он не станет 0, поэтому кажется, что 2-й вызов sort () и вызов merge () никогда не выполняются. Может кто-нибудь объяснить, какие шаги предпринимаются?

1 Ответ

2 голосов
/ 07 февраля 2020

Возьмем следующий массив: 

[4][2][5][1][3]

Мы собираемся разделить его пополам: 

[4][2][5]    [1][3]

И снова: 

[4][2]    [5]    [1]    [3]

И снова : 

[4]    [2]    [5]    [1]    [3]

Обратите внимание, что теперь у нас есть 5 отсортированных массивов (каждый длиной 1). Теперь пришло время объединить их, сортируя как мы go. Это очень простая (читай: низкая сложность) операция по объединению двух отсортированных массивов в новый отсортированный массив: 

[2][4]    [1][5]    [3]

Теперь у нас есть 3 отсортированных массива. Давайте объединим их снова: 

[1][2][4][5]    [3]

И в последний раз: 

[1][2][3][4][5]

Теперь оно отсортировано.

...