with Gnat.Io; use Gnat.Io;
procedure ShellSort is
    type IntArr is array (Integer range <>) of Integer;
    
    procedure Print_Arr (Arr : IntArr) is
    begin
        Put("[");
        for I in Arr'First .. Arr'Last - 1 loop
            Put(Arr(I));
            Put(", ");
        end loop;
        Put(Arr(Arr'Last));
        Put("]");
        New_Line;
    end Print_Arr;
    
    function Sort (Arr : in out IntArr) return IntArr is
        N : Integer := Arr'Length - 1;
        Gap : Integer := N / 2;
        Temp : Integer;
        J : Integer;
    begin
        while Gap > 0 loop
            for I in Gap .. N loop
                Temp :=  Arr(I);
                J := I;
                while J >= Gap and Arr(J - Gap) > Temp loop
                    Arr(J) := Arr(J - Gap);
                    J := J - Gap;
                    exit when J - Gap <= 0;
                end loop;
                
                Arr(J) := Temp;
            end loop;
            
            Gap := Gap / 2;
        end loop;
        
        return Arr;
    end;
    
    TestArr : IntArr(0..4) := (12, 34, 54, 2, 3);
begin
    Put("Array before sorting: ");
    Print_Arr(TestArr);
    Put("Array after sorting: ");
    Print_Arr(Sort(TestArr));
end ShellSort;