Merge Сортировать Базовый вариант (рекурсия) Проанализируйте

Question

Из книги Седжвик & Кевин Уэйн Алгоритмы 4-е издание

В рекурсии код базового варианта часть

if(end <= start) 
    { 
     return; 
    } 

Но я проверил end никогда не станет ниже индекс start. только end = start происходят, когда осталось только 1 элемент. Тогда почему <= меньше оператора, где работает только одно условие, равное = работает постоянно?

Предположим, что имеется массив a[8,5,3].

Теперь средняя точка первого индекса так после разрыва

a[8,5] and a[3] 

divide(a,0,1) and divide(a,2,2), merge(a,0,1,2) начало меньше, чем в конце divide(a,0,1) и start=end происходит в вызове функции divide(a,2,2).

Теперь середина - это 0-й индекс.

a[8] and a[5] 

divide(a,0,0) and divide(a,1,1), merge(a,0,0,1) здесь как в вызове функции start=end является единственно верным.

так буквально end никогда не становилась меньше start таким образом end<start никогда не бывает. только end=start.

Может ли кто-нибудь объяснить мне, почему мы используем оператор < (меньше) в базовом случае сортировки слияния?

Полных Рекурсивный Код

int divide(int a[], int start, int end) 
{ 
    int mid; 

    if(end<=start) 
    { 
     return; 
    } 
    else 
    { 
     mid = (start+end)/2; 
     divide(a, start, mid); 
     divide(a, mid+1, end); 
     merge(a, start, mid, end); 
    } 
} 

Answer 1

Это правильно, что divide функции никогда вызовов себя с аргументами так, что end < start. Таким образом, if-statement может быть также if (end == start).

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

void foo(int a[]) 
{ 
    divide(a, 5, 3); 
} 

Это может вызвать петлю Бесконечные если чек только был == вместо <=. Поэтому представляется более безопасным использование <=.

Исходный код также может быть переписано как:

int divide(int a[], int start, int end) 
{ 
    int mid; 

    if(end > start) 
    { 
     mid = (start+end)/2; 
     divide(a, start, mid); 
     divide(a, mid+1, end); 
     merge(a, start, mid, end); 
    } 
} 

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

BTW: Обратите внимание, что ваша функция, как говорят, возвращает int, но вы этого не делаете. Может быть, вы действительно хотите, чтобы это было: пустой разрыв (.....)

Answer 2

вы могли бы написать рекурсивную часть функции баррикад ниже

void divide(int a[], int start, int end) 
{ 
    int mid; 

    if(start < end) 
    { 
     mid = (start+end)/2; 
     divide(a, start, mid); 
     divide(a, mid+1, end); 
     merge(a, start, mid, end); 
    } 
}