재귀 상한 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); 
    } 

나는 그것을 병합 후 하위 어레이 길이 하나 (및 정의에 의한 분류)의 때까지 각이 반복, 아래로 2 개 작은 하위 어레이에 서브 어레이 나누기 및 does- 머지 소트 이해. 그러나이 정렬 함수가이 작업을 수행하는 데 사용하는 실제 메서드는 제가 따라하기가 어렵습니다. 어쩌면 내가 재귀 함수에 익숙하지 않기 때문에,하지만 누구나 작업 순서와 첫 번째 병합이 발생할 때의 인수가 무엇인지 밝힐 수 있는지 궁금합니다.

예를 들어, sort (aux, aux, low, mid)에 대한 FIRST 재귀 호출에 도달하면 - 작업을 중단하고 두 번째 정렬 및 병합 기능으로 진행하지 않고 대신 즉시 새로운 매개 변수? 이 경우 두 번째 호출을 정렬 할 때; sort (a, aux, mid + 1, high); 나오다?

도움 주셔서 감사합니다. 제가 여기에 게시 한 것은 이번이 처음입니다. 포맷 문제가 있다면 알려주세요. 이 (A, 보조, 낮은, 중반를) 정렬 할 FIRST 재귀 호출 안타 때

Answer 1

-이 작업을 중단 않으며하지 않고 즉시 새와 종류를 다시 호출, 두 번째 종류의 아래 병합 기능으로 이동 매개 변수?

• 예. 새 매개 변수에 대해 함수를 다시 호출 (재귀)하고 해당 부분을 정렬 할 때까지 내려갑니다.

이 경우, 두 번째 호출 정렬하는 것; 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. 

을 나는 그것이 간단한 예제를 실행하고 정말가 발생하는 경우 펜과 종이에 그것을 통해 실행하는 데 도움이 찾을 수 힘든 시간.