Почему эта рекурсия не получает своего базового варианта?

Question

Я пытаюсь реализовать функцию сортировки слиянием. Вот мой код:

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, но затем снова получает его начальное значение и превращается в бесконечное l oop.

Answer 1

То, что вы должны проверить, это

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

См. Полную реализацию сортировки слиянием здесь .

Редактировать Это предполагает u не входит в диапазон элементов, которые должны быть отсортированы. Если это так, вы должны проверить if (l < u).

Answer 2

Необходимо проверить, имеет ли диапазон хотя бы 2 элемента:

/* 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);
    }
}

Если верхняя граница u не включена в диапазон, код следует изменить на:

/* 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);
    }
}