Алгоритм слияния в C++

Question

У меня есть следующий код

#include <iostream>
using namespace std;
void merge(int c[],int a[],int n,int b[],int m){
         for (int i=0,j=0,k=0;k<n+m;k++){

             if (i==n) {  c[k]=b[j++]; continue;}
             if (j==m ){  c[k]=a[i++];continue;}

             c[k]=(a[i]<b[j])? a[i++]:b[j++];

         }



}
void mergesort(int a[],int b[],int l,int r){
if (l>r)  return ;
     int m=(l+r)/2;

     mergesort(b,a,l,m);
     mergesort(b,a,m+1,r);

 merge(a+l,b+l,m-l+1,b+m+1,r-m);

}
int main(){


    int a[]={12,4,2,5,3,6,7,8,10,11};
const   int n=sizeof(a)/sizeof(int);
int b[n];
mergesort(a,b,0,n-1);
    for (int i=0;i<n;i++){

        cout<<b[i]<< "  ";

    }




     return 0;
}

но вот такое предупреждение

1>------ Rebuild All started: Project: mergesort, Configuration: Debug Win32 ------
1>  mergesort.cpp
1>d:\c++_algorithms\mergesort\mergesort\mergesort.cpp(24): warning C4717: 'mergesort' : recursive on all control paths, function will cause runtime stack overflow
1>  mergesort.vcxproj -> D:\c++_algorithms\mergesort\Debug\mergesort.exe
========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========

пожалуйста, помогите мне исправить это

я обновил свой код

Answer 1

Функция mergesort() должна определить, было ли предложено отсортировать список по длине один, и если это так, немедленно вернуться. Кроме того, я могу ошибаться, но я думаю, что вызов merge() идет после рекурсивных вызовов mergesort().

Answer 2

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

В коде это будет означать проверку чего-то вроде

l==r

Также, по логике, слияние должно быть вызвано после того, как вы отсортировали два подмассива.

Answer 3

Ваш рекурсивный вызов должен иметь условие завершения, чтобы рекурсивные вызовы заканчивались в какой-то момент.
Я думаю, что добавление следующего условия в начале вашей функции слияния решает проблему:

if(l>r)
    return;

Answer 4

Вам нужно указать базовый регистр в вашей функции mergeSort! а также, в алгоритме mergeSort, вызов слияния происходит после рекурсивного вызова к левому и правому подмассивам