% Ordinamento ricorsivo di un vettore v
% 1. se il vettore ha lunghezza 1, ok
% 2. se il vettore e` lungo almeno 2 viene 
%    suddiviso in due meta`;
%    2.a ogni sottosequenza viene ordinata 
%        applicando ricorsivamente l'algoritmo
% 3. le due sottosequenze ordinate vengono 
%    fuse. Per fare questo si estrae ripetutamente
%    il minimo delle due sottosequenze e lo
%    si pone nella sequenza in uscita
% INPUT: 
% v: vettore da ordinare
% r: lunghezza del vettore

function v_ord=Msort(v,r)

m=length(v) ;
if m==1
    v_ord=v ;
    disp(m) ;
    
else
    disp(['Step ricorsione: ' , num2str(r)]) ;
    % Divido il vettore in due parti ("uguali"), v1 e v2 (DIVIDE)
    punto_medio=round(m/2) ;
    % Applico Msort a v1 e a v2
    v1=Msort(v(1:punto_medio),punto_medio) ;
    v2=Msort(v(punto_medio+1:end),punto_medio) ; 

    % IMPERA 

    % ordinamento
    m1=length(v1) ;
    m2=length(v2) ;
    i=1 ;
    j=1 ;
    v_ord=[] ;
    while i<=m1 && j<=m2
        if v1(i) < v2(j)
            v_ord=[v_ord v1(i)] ;
            i=i+1 ;
        else
            v_ord=[v_ord v2(j)] ;
            j=j+1 ;
        end
    end
    if i <= m1
        v_ord=[v_ord v1(i:end)] ;
    else
        v_ord=[v_ord v2(j:end)] ;
    end
    
   assert(length(v_ord) == m1+m2)
    
end
end