Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [С++] Merge sort Порядок запуска рекур. функции

Автор: agl 6.5.2007, 18:53

Не могу понять последовательность вызова функции(функция merge_sort вызывает сама себя и функцию merge). Понимаю что писать не мало, но кто может объясните пожалуйста. Заранее спасибо.

Код


void merge_sort(int *a, long int low_bound, long int upper_bound)
{
     long int split;
     
     if(low_bound < upper_bound) 
     {
          split = (low_bound + upper_bound) / 2;    
          merge_sort(a, low_bound, split);         
          merge_sort(a, split+1, upper_bound);     
          merge(a, low_bound, split, upper_bound);  
     }
}

Автор: agl 7.5.2007, 12:44

Попробую конкретизировать вопрос:
насколько я пономаю, если low_bound меньше upper_bound, тогда происходит рекурсивные вызовы:
вызываем фумкцию merge_sort(a, low_bound, split); - вызов данной функции с параметрами low_bound, split происходит до тех пор, пока не получаем что low_bound равнен upper_bound. Когда они равны - происходит возврат(выход) из данной рекурсивной ветки. Возвращаемся в обратном порядке, по ходу возврата вызывается merge_sort(a, split+1, upper_bound); - данный вызов влечет за собой опять ветку вызовов, как описано выше, до тех пор, пока low_bound равнен upper_bound, а затем начинается возврат ... После возврате из merge_sort(a, split+1, upper_bound); происходит вызов функции merge.
Рекурсивные задачи такого уровня меня путают smile

Подскажите пожалуйста, ход моих мыслей правильный?