Два рекурсивных вызова в путанице функции сортировки слиянием
Некоторое время я не общался с Алгоритмами и сейчас начинаю пересматривать свои концепции. К моему удивлению, последнее, что я помню о своих навыках рекурсии, было то, что я был хорош в этом, но не больше Итак, у меня есть основной вопрос для вас, ребята, который сбивает меня с толку. Пожалуйста, сначала посмотрите код ниже.
private void mergesort(int low, int high) {
if (low < high) {
int middle = (low + high)/2 ;
System.out .println ("Before the 1st Call");
mergesort(low, middle);
System.out .println ("After the 1st Call");
mergesort(middle+1, high);
System.out .println ("After the 2nd Call");
merge(low, middle, high);
}
}
Вызов функции
mergesort(0,7);
И вывод
Before the 1st Call
Before the 1st Call
Before the 1st Call
After the 1st Call
After the 2nd Call
After the 1st Call
Before the 1st Call
After the 1st Call
After the 2nd Call
After the 2nd Call
After the 1st Call
Before the 1st Call
Before the 1st Call
After the 1st Call
After the 2nd Call
After the 1st Call
Before the 1st Call
After the 1st Call
After the 2nd Call
After the 2nd Call
After the 2nd Call
В приведенном выше коде и результате меня смущает второй рекурсивный вызов. Я понимаю последовательность до четвертой строки вывода (т.е. после 1-го вызова). Но я не могу понять, почему он выводит (после 2-го вызова) после (после 1-го вызова). Согласно тому, что я понимаю из кода После вывода (после 1-го вызова) должна быть вызвана функция слияния с параметром (middle + 1, high), и она должна вывести (до 1-го вызова) и перейти к рекурсивному вызову с помощью mergesort (низкий, средний). Я совместим с одним рекурсивным вызовом функций и понимаю и синхронизируюсь с примером Форе Фибоначчи.