naturalsort

program merge;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

type
   TIntArr = array of Integer;

procedure PrintToIndex(A: TIntArr; Index: Integer; MessageToUser: string);
var
   i: Integer;
begin
   Writeln;
   Write(MessageToUser);
   for i := 0 to Index do
      Write(A[i], ' ');
   Writeln;
end;


function FindFinalSequenceIndex(const UserArray: TIntArr): Integer;
var
   HighIndex, Index, i: Integer;
   IsEndOfTheSequence: Boolean;
begin
   Index := 0;
   HighIndex := High(UserArray);
   IsEndOfTheSequence := False;
   while (Index < HighIndex) and (not IsEndOfTheSequence) do
      if UserArray[Index] <= UserArray[Index + 1] then
         Inc(Index)
      else
         IsEndOfTheSequence := True;
   //тут уже есть индекс, где заканчивается последовательность
   for i := 0 to Index do
      Write(UserArray[i], ' ');
   Write(' |  ');
   if Index = HighIndex then
      FindFinalSequenceIndex := -1
   else
      FindFinalSequenceIndex := Index + 1;
end;



function MergeSort(UserArray: TIntArr): TIntArr;
var
   LeftIndex, RightIndex, SortArrayIndex, IndexOfTheSequence: Integer;
   UserArrayLen, LeftPartLen, RightPartLen: Integer;
   LeftPart, RightPart: TIntArr;
begin
   UserArrayLen := Length(UserArray);
   if UserArrayLen > 1 then
   begin
      IndexOfTheSequence := FindFinalSequenceIndex(UserArray);
      if IndexOfTheSequence <> -1 then//если равен -1, то массив у нас уже отсортирован и ничего не надо делать
      begin
         LeftPart := copy(UserArray, 0, IndexOfTheSequence);
         RightPart := MergeSort(copy(UserArray, IndexOfTheSequence, UserArrayLen));
         LeftPartLen := Length(LeftPart);
         RightPartLen := Length(RightPart);

         Writeln;
         PrintToIndex(LeftPart, LeftPartLen - 1, 'Left part: ');
         PrintToIndex(RightPart, RightPartLen - 1, 'Right part: ');

         LeftIndex := 0;
         RightIndex := 0;
         SortArrayIndex := 0;
         SetLength(UserArray, LeftPartLen + RightPartLen);
         while (LeftIndex < LeftPartLen) and (RightIndex < RightPartLen) do
         begin
            if LeftPart[LeftIndex] <= RightPart[RightIndex] then
            begin
               UserArray[SortArrayIndex] := LeftPart[LeftIndex];
               Inc(LeftIndex);
            end
            else
            begin
               UserArray[SortaArrayIndex] := RightPart[RightIndex];
               Inc(RightIndex);
            end;
            Inc(SortArrayIndex);
         end;

         while LeftIndex < LeftPartLen do
         begin
            UserArray[SortArrayIndex] := LeftPart[LeftIndex];
            Inc(LeftIndex);
            Inc(SortArrayIndex);
         end;

         while RightIndex < RightPartLen do
         begin
            UserArray[SortArrayIndex] := RightPart[RightIndex];
            Inc(RightIndex);
            Inc(SortArrayIndex);
         end;
         PrintToIndex(UserArray, UserArrayLen - 1, 'After merge: ');
         //изменить массив UserArray, записать туда начало и смерженые правую и левую часть

         Writeln('----------');
      end;
   end
   else
      Write(UserArray[0]);
   MergeSort := UserArray;
end;

var
   Arr: TIntArr;
   i, N: Integer;
begin
   Writeln('Enter n');
   Readln(N);

   SetLength(Arr, N);
   Writeln('Enter elems');
   for i := 0 to N - 1 do
      Readln(Arr[i]);

   PrintToIndex(MergeSort(Arr), Length(Arr) - 1, '');
   Readln;
end.