MergeSort

FilesMergeSort.pas

// written by github.com/notaLonelyDay
program MergeSortConsole;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils;

const
  RANDOM_MAX = 100;
  MAIN_FILENAME = 'int_file';
  HELPER1_FILENAME = 'helper_file_1';
  HELPER2_FILENAME = 'helper_file_2';

type
  TTypedIntFile = File of Integer;

var
  MainFile, Helper1, Helper2: TTypedIntFile;
  i, t, j: Integer;

procedure createRandomIntTypedFile(filename: String; size: Integer);
var
  f: TTypedIntFile;
  i, rnd: Integer;
begin
  AssignFile(f, filename);
  Rewrite(f);
  for i := 1 to size do
  begin
    rnd := Random(RANDOM_MAX);
    Write(f, rnd);
  end;
  Writeln;

  Close(f);
end;

procedure writeMainFile;
begin
  Reset(MainFile);
  for i := 1 to Filesize(MainFile) do
  begin
    Read(MainFile, t);
    Write(t, ' ');
  end;
  Writeln;
  Reset(MainFile);
end;

procedure mergeSortFile(var f, h1, h2: TTypedIntFile);
var
  fSize, pairSize: Integer;
  h1Size: Integer;
  h2Size: Integer;
  i: Integer;
  temp, helper1Pointer, helper2Pointer, inPair1Pointer, inPair2Pointer,
    splitPointer: Integer;

  cache1, cache2: Integer;
begin
  pairSize := 1;
  fSize := Filesize(f);
  while (pairSize < fSize) do
  begin
    //writeMainFile;
    // splitting
    Reset(f);
    Rewrite(h1);
    Rewrite(h2);
    splitPointer := 0;

    // Делим главный файл в два вспамогательных
    while (splitPointer < fSize) do
    begin
      i := 0;
      while (splitPointer < fSize) and (i < pairSize) do
      begin
        read(f, temp);
        write(h1, temp);
        inc(i);
        inc(splitPointer);
      end;

      i := 0;
      while (splitPointer < fSize) and (i < pairSize) do
      begin
        read(f, temp);
        write(h2, temp);
        inc(i);
        inc(splitPointer);
      end;
    end;

    Reset(h1);
    Reset(h2);
    Rewrite(f);

    h1Size := Filesize(h1);
    h2Size := Filesize(h2);

    // updating caches
    Read(h1, cache1);
    Read(h2, cache2);

    // merging
    helper1Pointer := 0;
    helper2Pointer := 0;
    while (helper1Pointer < h1Size) and (helper2Pointer < h2Size) do
    begin

      inPair1Pointer := 0;
      inPair2Pointer := 0;
      // Слили все пары для которых совместные пары
      while (helper1Pointer < h1Size) and (helper2Pointer < h2Size) and
        (inPair1Pointer < pairSize) and (inPair2Pointer < pairSize) do
      begin
        if (cache1 < cache2) then
        begin
          Write(f, cache1);
          inc(helper1Pointer);
          inc(inPair1Pointer);
          if not eof(h1) then
            Read(h1, cache1);
        end
        else
        begin
          Write(f, cache2);
          inc(helper2Pointer);
          inc(inPair2Pointer);
          if not eof(h2) then
            Read(h2, cache2);
        end;
      end;

      while (helper1Pointer < h1Size) and (inPair1Pointer < pairSize) do
      begin
        Write(f, cache1);
        inc(helper1Pointer);
        inc(inPair1Pointer);
        if not eof(h1) then
          Read(h1, cache1);
      end;

      while (helper2Pointer < h2Size) and (inPair2Pointer < pairSize) do
      begin
        Write(f, cache2);
        inc(helper2Pointer);
        inc(inPair2Pointer);
        if not eof(h2) then
          Read(h2, cache2);
      end;

    end;

    while (helper1Pointer < h1Size) do
    begin
      Write(f, cache1);
      inc(helper1Pointer);
      if not eof(h1) then
        Read(h1, cache1);
    end;

    while (helper2Pointer < h2Size) do
    begin
      Write(f, cache2);
      inc(helper2Pointer);
      if not eof(h2) then
        Read(h2, cache2);
    end;
    pairSize := pairSize * 2;

  end;

end;

procedure test;
var
  prev, cur: Integer;

begin
  Reset(MainFile);
  Read(MainFile, prev);
  for i := 2 to Filesize(MainFile) do
  begin
    Read(MainFile, cur);
    if (cur < prev) then
    begin
      Writeln('Error!');
      Exit;
    end;
    prev := cur;
  end;
  Writeln('OK!');
  Writeln('Test passed!');

end;

begin
  for j := 1 to 100000 do
  begin
    Writeln(j);
    createRandomIntTypedFile('int_file', 1);

    // Exit;
    AssignFile(MainFile, MAIN_FILENAME);
    Reset(MainFile);

    AssignFile(Helper1, HELPER1_FILENAME);
    Rewrite(Helper1);

    AssignFile(Helper2, HELPER2_FILENAME);
    Rewrite(Helper2);

    // Reset(MainFile);
    // for i := 1 to Filesize(MainFile) do
    // begin
    // Read(MainFile, t);
    // Write(t, ' ');
    // end;
    // writeln;
    // Reset(MainFile);

    mergeSortFile(MainFile, Helper1, Helper2);

    test;
  end;
  Readln;

end.