function merge_sort(input, inizio, fine): void
    var inizio,fine,medio: integer
    var input: array(1..fine) of integer
    begin
    if(inizio<fine) then
        medio := (inizio + fine) / 2
        merge_sort(input, inizio, medio)
        merge_sort(input, medio + 1, fine)
        merge(input, inizio, fine)
    endif
end

function merge(input, inizio, fine): void
    var inizio, fine, medio: integer
    var input: array(1..fine) of integer
    var i1,i2,i3: integer
    var temp: array(1..fine-inizio+1) of integer
    begin

    medio := ((inizio+fine) / 2)
    i1 := 0             //indice array temp
    i2 := inizio        //indice sottoarray sx
    i3 := medio + 1     //indice sottoarray dx

    while ( i2 <= medio .AND. i3 <= fine )do
        if ( input[i2] < input[i3] ) then
            temp[i1] = input[i2]
            i1:=i1+1
            i2:=i2+1
        else
            temp[i1] = input[i3]
            i1:=i1+1
            i3:=i3+1
        endif
    end while
    // Merge degli elementi rimasti a sinistra
    while ( i2 <= medio ) do
        temp[i1] = input[i2]
        i1:=i1+1
        i2:=i2+1
    end while

    // Merge degli elementi rimasti a destra
    while ( i3 <= fine )do
        temp[i1] = input[i3]
        i1:=i1+1
        i3:=i3+1
    end while

     // Sposto tutti gli elementi dall'array temporaneo all'array originale
    i:=inizio
    for i to fine do
        input[i] := temp[i-inizio]
    end for
end