программа застряла в конце рекурсии в (рекурсивной) вставке

Question

Я пытаюсь реализовать сортировку вставкой в ​​C ++.

#include <iostream>
#include <vector>
using namespace std;

vector<int> insertionSort(vector<int>& A,int p,int r)
{ 
    for(auto x=p;x<=r;++x) cout<<A[x]<<' ';
    cout<<endl;  
    if(p<r-1) insertionSort(A,p,r-1);
    cout<<"flag";
    int key=A[r];
    int i=r-1;
    while(i>p)
    {
        if(key<=A[i])
        {
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=key;
    }
    return A;
}

int main()
{
    vector<int> A {22,2,31,41,59,90,11,26,41,58};
    insertionSort(A,0,A.size()-1);
    for(auto x:A) cout<<x<<' ';
    cout<<endl;
}

Вывод:

22 2 31 41 59 90 11 26 41 58
22 2 31 41 59 90 11 26 41
22 2 31 41 59 90 11 26
22 2 31 41 59 90 11
22 2 31 41 59 90
22 2 31 41 59
22 2 31 41
22 2 31
22 2
^ C⏎

Как вы можете видеть, он застревает в конце рекурсии (он не go после флага заявление) и я должен вручную завершить выполнение. Если мое понимание верно, когда рекурсия достигает своего конца, следующие операторы выполняются в каждом из стеков вызовов. Пожалуйста, помогите мне разобраться в проблеме. Любая помощь будет оценена.

Answer 1

Спасибо всем за полезные комментарии. Как они сказали, программа, похоже, застряла из-за бесконечного l oop, которое произошло, когда блок if не был выполнен. Поэтому я добавил break и также поместил оператор вставки вне блока while. Вот исправленный код:

vector<int> insertionSort(vector<int>& A,int p,int r)
{   
    if(p<r-1) insertionSort(A,p,r-1);
    int key=A[r];
    int i=r-1;
    while(i>=p)
    {
        if(key<A[i])
        {
            A[i+1]=A[i];
            i=i-1;
        }
        else break;
    }
    A[i+1]=key;
    return A;
}