이 재귀가 기본 사례를 얻지 못하는 이유는 무엇입니까? (Why is this Recursion not getting its base case?)

문제 설명

이 재귀가 기본 사례를 얻지 못하는 이유는 무엇입니까? (Why is this Recursion not getting its base case?)

병합 정렬 기능을 구현하려고 합니다. 내 코드는 다음과 같습니다.

void
merge_sort(int a[], int l, int u)
{
  int mid = (l + u) / 2;
  if (mid) {
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, u);
    merge(a, l, mid, u);
  }
}

mid 값이 0인 것을 확인했지만 다시 초기 값을 가져오고 무한 루프로 바뀝니다.

참조 솔루션

방법 1:

What you are supposed to check is

if (mid != l) {
    // ...
}

See a complete merge sort implementation here.

Edit This assumes u is not in the range of elements that are meant to be sorted. If it is, you should testif (l < u).

방법 2:

You must check if the range has at least 2 elements:

/* sort a range of elements from `l` to `u` inclusively */
void merge_sort(int a[], int l, int u) {
    if (l < u) {
        int mid = l + (u ‑ l) / 2;
        merge_sort(a, l, mid);
        merge_sort(a, mid + 1, u);
        merge(a, l, mid, u);
    }
}

If the upper bound u is not included in the range, the code should be changed to:

/* sort a range of elements from `l` included to `u` excluded */
void merge_sort(int a[], int l, int u) {
    if (u ‑ l >= 2) {
        int mid = l + (u ‑ l) / 2;
        merge_sort(a, l, mid);
        merge_sort(a, mid, u);
        merge(a, l, mid, u);
    }
}

(by Nastik、Ayxan Haqverdili、chqrlie)

참조 문서

1. Why is this Recursion not getting its base case? (CC BY‑SA 2.5/3.0/4.0)