Iteracyjne sortowanie przez scalanie

Question

const maxA=1000;
type TArray=array[0..maxA]of real;

procedure merge(var A:TArray;p,q,r:integer);
var n1,n2,i,j,k:integer;
       B:TArray;
begin
      n1:=q-p+1;
      n2:=r-q;
     for i:=p to r do 
         B[i-p+1]:=A[i];
     i:=1;
     j:=n1+1;
    k:=p;
     while((i<=n1)and(j<=n1+n2)) do 
     begin
         if(B[i]<=B[j]) then
         begin
              A[k]:=B[i];
              i:=i+1;
         end
         else
         begin
            A[k]:=B[j];
            j:=j+1;
         end;
         k:=k+1;
     end;
     while(i<=n1) do
     begin
          A[k]:=B[i];
          i:=i+1;
          k:=k+1;
     end; 
     while(j<=n1+n2) do
     begin
          A[k]:=B[j];
          j:=j+1;
          k:=k+1;
     end; 
end;

procedure mergeSort(var A:TArray;size:integer)
var curr,left,mid,right:integer;
begin
     curr:=1;
     while(curr<=size-1)  do 
     begin
          left:=0;
          while(left<size-1) do
          begin
              mid:=left+curr-1;
               if(left+2*curr-1<size-1) then
                  right:=left+2*curr-1
               else right:=size-1;
                merge(A,left,mid,right);
              left:=left+2*curr;      
          end;
          curr:=curr*2;
     end;
end;

Problem w tym że procedura sortująca napisana jest dla tablic indeksowanych od zera
a procedura scalająca napisana jest dla tablic indeksowanych od jedynki

Przypuśćmy że chcemy aby tablica była indeksowana od jedynki
Jak przesunąć indeksy w procedurze sortującej

Jaka jest złożoność procedury sortującej
Mam wątpliwości czy tak napisana procedura sortująca ma nadal złożoność O(nlogn)

Skoro koniecznie chcecie C to przepiszę interesującą mnie procedurę na C
 

                            
void mergeSort(double* A,int size)
{
      int curr,left,mid,right;
      curr=1;
      while(curr<=size-1) 
      {
        left=0;
        while(left<size-1)
        {
          mid=left+curr-1;
          if(left+2*curr-1<size-1)
             right=left+2*curr-1; 
          else right=size-1;              
          merge(A,left,mid,right);
          left=left+2*curr;
         }
         curr=curr*2;
        }
      } 

Answer 1

Warunek dla tej wewnętrznej pętli był źle skonstruowany i dlatego miałem problemy z przesunięciem indeksów