Merge сортировать Рекурсию Ошибка

Question

Mergesort(a,p,r){ 
    if(p<r){ 
     int q=[p+r]/2; 
     Mergesort(a,p,q); 
     Mergesort(a,q+1,r); 
     Merge(a,p,q,r); 

Это из книги Введение алгоритмам: Cormen в этом я не могу понять, рекурсивный вызов алгоритма

    2 4 1 6 8 5 3 7 
       2 4 1 6   
       2 4 
      2 

сортировки слияния в первом рекурсивном вызове я получил ДО три тогда, где контроль идет отсюда, пораженный 2, вызовет ли он следующую функцию mergesort (a, q + 1, r) и слияние (a, p, q, r)?

Answer 1

Предположим, что ваш массив равен a = { 2, 4, 6, 1, 8, 5, 3, 7 }. Я поменял два элемента массива, предложенные вами. Теперь, как следует, что именно делает ваша программа, вызывается после вызова.

---

При первом вызове p=0, q=7: ваш массив - это вход. При втором вызове p=0, q=3, на третьем p=0, q=1.

На четвертом вызове p=0, q=0: вход является подмассивом { 2 }. Этот массив имеет только один элемент, поэтому сортируется: строка if(p<r) гарантирует, что четвертый вызов заканчивается здесь, и управление возвращается к третьему вызову.

Третий вызов имеет вход { 2, 4 }. Мы только что закончили линию Mergesort(a,p,q);, таким образом, мы знаем, что первая половина ввода сортируется. пятый звонок (линия Mergesort(a,q+1,r);) теперь будет сортировать вторую половину.

На пятом вызове p=1, q=1. Ввод снова представляет собой массив длиной 1, который сортируется по умолчанию. Управление возвращается к третьему вызову.

Третий вызов теперь оценивает линию Merge(a,p,q,r);. Первая половина сортируется, вторая половина сортируется: Merge(a,p,q,r); берет эти две половины и сдвигает элемент, убедившись, что всего подмассива из индекса p для индекса r сортируется. Третий вызов заканчивается.

Второй звонок имел { 2, 4, 6, 1 } имеет вход. Первая половина сортируется, теперь остается вторая половина: после этого наберите вход { 2, 4, 1, 6 }. После того, как Merge называется входом, становится { 1, 2, 4, 6 }, а второй вызов заканчивается, возвращая управление первому вызову.

Первый звонок теперь должен сортировать вторую половину его вход, который, кстати, является целым массивом. Это делается по-прежнему.