code 36405;
procedure MERGESORT(A,P,LOW,UP);value LOW,UP;
integer LOW,UP;array A;integer array P;
begin integer I,L,R,PL,PR,LO,STEP,STAP,UMLP1,UMSP1,REST,RESTV;
    boolean ROUT,LOUT; integer array HP[LOW:UP];
    procedure MERGE(LO,LS,RS);value LO,LS,RS;integer LO,LS,RS;
    begin L:=LO; R:=LO+LS; LOUT:=ROUT:=false;
        for I:=LO,I+1 while ^(LOUT or ROUT) do 
        begin PL:=P[L];PR:=P[R];if A[PL]>A[PR] then 
            begin HP[I]:=PR;R:=R+1;ROUT:=R=LO+LS+RS end else 
            begin HP[I]:=PL;L:=L+1;LOUT:=L=LO+LS    end 
        end FOR I;
        if ROUT then 
        begin for I:=LO+LS-1 step -1 until L do 
            P[I+RS]:=P[I];R:=L+RS
        end;
        for I:=R-1 step -1 until LO do P[I]:=HP[I];
    end MERGE;
    for I:=LOW step 1 until UP do P[I]:=I;RESTV:=0;
    UMLP1:=UP-LOW+1;
    for STEP:=1, STEP*2 while STEP < UMLP1 do 
    begin STAP:=2*STEP;UMSP1:=UP-STAP+1;
        for LO:=LOW step STAP until UMSP1 do 
        MERGE(LO,STEP,STEP); REST:=UP-LO+1;
        if REST>RESTV & RESTV>0 then MERGE(LO,REST-RESTV,RESTV);
        RESTV:=REST
    end FOR STEP
end MERGESORT

        eop