Процесс сортировки слиянием

Question

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

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);          //talking about 
        sort(arr , m+1, r);       //this part 

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

Единственная модель, которая приходит мне в голову, которая разветвляет массив, это (учитывая массив {48, 34, 4, 1}):

m(a, l(0), r(3));
  m(a, l(0), m(1));
    m(a, l(0), m(0));
    m(a, m+1(1), r(1));
  m(a, m+1(2), r(3));
    m(a, l(2), m(2));
    m(a, m+1(3), r(3);

Это порядок, в котором выполняются звонки?вызывает:

    sort(arr, l, m);      
    sort(arr , m+1, r);

Также я не могу понять, почему, когда аргументы метода не удовлетворяют условию if (l<r), алгоритм переходит обратно на другую сторону массива и сортирует его.

Answer 1

В какой-то момент в рекурсии sort (...) ничего не делает и просто возвращает (потому что l == r) и 2 метода sort (...) выполнены.После этого слияние вступает в действие, которое ничего не делает, кроме как расположить 2 элемента в правильном порядке.После того, как это произошло, какой-то другой метод sort (...) из предыдущего вызова завершился и т. Д.