문제 설명
Java 병합 정렬의 정렬 부분 이해 (Understanding the sort part of Java Merge sort)
병합 정렬의 병합 부분이 어떻게 작동하는지 이해하지만 어떤 이유로 병합 기능이 호출되기 전에 발생하는 재귀/나누기 부분을 감쌀 수 없습니다. 아래 샘플 코드를 사용하여 다양한 변수의 값을 추적하려고 시도했지만 무슨 일이 일어나고 있는지 완전히 이해할 수 없었습니다.
public void sort(int arr[], int l, int r) {
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
내 보기에는 m이 계속 정렬로 전달되는 것 같습니다. 0이 될 때까지 두 번째 sort() 호출과 merge() 호출이 실행되지 않는 것처럼 보입니다. 수행된 단계를 설명할 수 있습니까?
참조 솔루션
방법 1:
Take the following array:
[4][2][5][1][3]
We're going to split it in half:
[4][2][5] [1][3]
And again:
[4][2] [5] [1] [3]
And again:
[4] [2] [5] [1] [3]
Notice how we now have 5 sorted arrays (each of length 1). Now it's time to merge them together, sorting as we go. It's a very simple (read: low time‑complexity) operation to merge two sorted arrays into a new sorted array:
[2][4] [1][5] [3]
Now we have 3 sorted arrays. Let's merge them again:
[1][2][4][5] [3]
And one final time:
[1][2][3][4][5]
It's now been sorted.
(by user3552172、Michael Bianconi)