algorithme mergesort en C++

Question

j'ai code suivant

#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; 
} 

mais voici un tel avertissement

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 ========== 

s'il vous plaît aidez-moi à le réparer

j'ai mis à jour mon code

Answer 1

mergesort() doit détecter s'il a été demandé de trier une liste de longueur un, et si oui, retourner immédiatement. En outre, je peux me tromper, mais je pense que l'appel à merge() va après les appels récursifs à mergesort().

Answer 2

Votre appel récursif doit avoir une condition de fin de sorte que les appels récursifs se terminent à un moment donné.
Je pense ajouter la condition suivante au début de votre mergesort fonction résout le problème:

if(l>r) 
    return; 

Answer 3

vous devez spécifier un cas de base dans votre fonction mergesort! et aussi, dans l'algorithme mergeSort, l'appel à fusionner vient après l'appel récursif aux sous-matrices gauche et droite

Answer 4

Vous devez avoir un cas de base, ce qui signifie probablement que vous devriez vérifier si la taille du tableau vous est le tri est = 1, et si c'est le cas, vous renvoyez cet élément particulier lui-même.

Dans le code, cela signifierait vérifier quelque chose comme

l==r 

En outre, logiquement, la fusion devrait être appelée après avoir trié les deux sous-réseaux.