mynaturalsort

program natural;

{$APPTYPE CONSOLE}

uses
  System.SysUtils;

type
   TArray = array of Integer;

procedure Print(A: TArray);
var
   LastIndex, N, i: Integer;
begin
   LastIndex := High(A);
   for i := 0 to LastIndex do
      Write(A[i], ' ');
   Writeln;
end;

function MergeTwoIntoOne(First, Second: TArray): TArray;
var
   i, j, FirstLen, SecondLen, TotalIndex, FirstIndex, SecondIndex: Integer;
   Total: TArray;

begin
   FirstLen := Length(First);
   SecondLen := Length(Second);

   FirstIndex := 0;
   SecondIndex := 0;
   TotalIndex := 0;

   SetLength(Total, FirstLen + SecondLen);

   while (FirstIndex < FirstLen) and (SecondIndex < SecondLen) do
   begin
      if First[FirstIndex] < Second[SecondIndex] then
      begin
         Total[TotalIndex] := First[FirstIndex];
         Inc(FirstIndex);
      end
      else
      begin
         Total[TotalIndex] := Second[SecondIndex];
         Inc(SecondIndex);
      end;
      Inc(TotalIndex);
   end;

   while FirstIndex < FirstLen do
   begin
      Total[TotalIndex] := First[FirstIndex];
      Inc(FirstIndex);
      Inc(TotalIndex);
   end;

   while SecondIndex < SecondLen do
   begin
      Total[TotalIndex] := Second[SecondIndex];
      Inc(SecondIndex);
      Inc(TotalIndex);
   end;

   MergeTwoIntoOne := Total;
end;

function FindSeparator(A: TArray; From: Integer): Integer;
var
   i, Index, Len: Integer;
   ShouldEnd: Boolean;
begin
   Index := From;
   Len := Length(A);
   ShouldEnd := False;
   while (Index < Len) and not ShouldEnd do
      if A[Index] >= A[Index - 1] then
         Inc(Index)
      else
         ShouldEnd := True;

   FindSeparator := Index;
end;

procedure MergeSort(Initial: TArray);
var
   i, j, InitialLen, CurIndex, FirstSeparator, SecondSeparator: Integer;
   First, Second, Total: TArray;
begin
   InitialLen := Length(Initial);
   repeat
      FirstSeparator := FindSeparator(Initial, 1);
      SecondSeparator := FindSeparator(Initial, FirstSeparator + 1);

      First := Copy(Initial, 0, FirstSeparator);
      Second := Copy(Initial, FirstSeparator, SecondSeparator - FirstSeparator);

      Total := MergeTwoIntoOne(First, Second);

      for i := 0 to Length(Total) - 1 do
         Initial[i] := Total[i];

   until SecondSeparator = InitialLen;
end;

var
   N, i: Integer;
   A, Res, d, c: TArray;
begin
   Writeln('Enter N:');
   Readln(N);
   SetLength(A, N);

   Randomize;
   for i := 0 to N - 1 do
   begin
      //Write(i, 'th > ');
      //Readln(A[i]);
      A[i] := Random(15);
   end;

   Writeln('Unsorted array:');
   Print(A);

   MergeSort(A);
   Writeln('Sorted array:');
   Print(A);
   Readln;
end.