"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"