RecursiveInsertionSort

#include <iostream>
#include <string>
using namespace std;
int N=10;
void display(int arr[],int n);

void insertionSortRecursive(int arr[], int n){
    if (n > 1){
        // Ordina i primi n-1 elementi
        insertionSortRecursive( arr, n-1 );

        // Inserisci l'ultimo elemnto alla sua posizione corretta nell'array selezionato
        int last = arr[n-1];
        int j = n-2;
        /*
        Muovi gli elmenti di arr[0..i-1] che sono più grandi di key,
        di una posizione avanti alla loro posizione corrente
        */
        while (j >= 0 && arr[j] > last){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = last;
        //debug
        display(arr,n);cout<<"|"<<last;  cout<<endl;
    }
}
int main(){
    int arr[10]={4,8,10,5,3,644,55,3,1};
    display(arr,N);cout<<endl;
    cout<<"========="<<endl;
    insertionSortRecursive(arr,N);
    cout<<"========="<<endl;
    display(arr,N);cout<<endl;
}

void display(int arr[],int n){
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";

    }