Рекурсивный сверху вниз mergesort

Question

Я пытаюсь разгадать рекурсивную функцию сортировки, которая является частью алгоритма mergesort. Вот код, который у меня есть, который я почти уверен в правильности (после онлайн-курса).

private static void sort(Comparable[] a, Comparable[] aux, int low, int high) { 
     if (high <= low) return; 
     int mid = low + (high - low)/2; 
     sort (a, aux, low, mid); 
     sort (a, aux, mid+1, high); 
     merge(a, aux, low, mid, high); 
    } 

Я понимаю, что это does- слияние разбивает каждый подмассив вниз на 2 меньшие подмассивы, повторяя это до тех пор, пока Подмассивы имеют длину один (и по определению отсортированной), а затем сливается. Тем не менее, фактический МЕТОД, который эта функция сортировки использует для достижения этого, мне трудно следовать. Может быть, потому, что я не привык к рекурсивным функциям, но мне было интересно, может ли кто-нибудь осветить порядок операций и какие аргументы возникают при первом слиянии.

Например, когда он обращается к FIRST-рекурсивному вызову сортировки (a, aux, low, mid) - он прерывает операцию, а не переходит к второму сортированию и функциям слияния ниже, вместо этого немедленно вызывает сортировку с помощью новые параметры? Когда в этом случае второй вызов будет сортироваться; sort (a, aux, mid + 1, high); произойти?

Спасибо за любую помощь. Это первый раз, когда я опубликовал здесь, если есть какие-либо проблемы с форматированием, пожалуйста, дайте мне знать.

Answer 1

Когда он обращается к первому рекурсивному вызову сортировки (a, aux, low, mid) - он прерывает операцию, а не переходит к второму сортированию и функциям слияния ниже, вместо этого немедленно вызывает сортировку с новым параметры?

• Да. он снова вызывает функцию (Рекурсия) для новых параметров, идите вниз, пока она не сортирует эту часть.

Когда в этом случае будет второй вызов сортировки; sort (a, aux, mid + 1, high); произойти?

• После первого вызова выполняется. (Когда первая часть закончит сортировку).

Answer 2

Комментариев поясняющих каждый шаг в случае, если вы не получили какой-либо:

if (high <= low) return; // if your high and low numbers are the same then this part of the loop is finished and it will start going back up 
int mid = low + (high - low)/2;//sets mid 
sort (a, aux, low, mid);//recursively calls itself so that it will eventually hit the first if. This handles from low to mid 
sort (a, aux, mid+1, high); //this handles from mid+1 to high 
merge(a, aux, low, mid, high); //This is where the merge starts. 

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