NUMAL Section 3.3.1.1.3.1

BEGIN SECTION : 3.3.1.1.3.1 (November, 1976)

AUTHORS: J.J.G. ADMIRAAL, A.C. YSSELSTEIN.

CONTRIBUTOR: J.J.G. ADMIRAAL.

INSTITUTE: UNIVERSITY OF AMSTERDAM.

RECEIVED: 761101.

BRIEF DESCRIPTION:
    THIS SECTION CONTAINS THREE PROCEDURES FOR SORTING THE
    ELEMENTS OF A VECTOR AND CORRESPONDINGLY PERMUTING THE
    ELEMENTS OF A VECTOR OR A MATRIX ROW.
    A) MERGESORT DELIVERS A PERMUTATION OF INDICES
       CORRESPONDING TO SORTING THE ELEMENTS OF A GIVEN
       VECTOR INTO NON-DECREASING ORDER.
    B) VECPERM PERMUTES THE ELEMENTS OF A GIVEN VECTOR
       CORRESPONDING TO A GIVEN PERMUTATION OF INDICES.
    C) ROWPERM PERMUTES THE ELEMENTS OF A GIVEN ROW OF A
       MATRIX CORRESPONDING TO A GIVEN PERMUTATION OF
       INDICES.

KEYWORDS:
    SORTING,
    PERMUTING.


SUBSECTION: MERGESORT.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:

    "PROCEDURE" MERGESORT(VEC1,VEC2,LOW,UPP);
    "VALUE" LOW,UPP;"INTEGER" LOW,UPP;"ARRAY" VEC1;
    "INTEGER""ARRAY" VEC2; "CODE" 36405;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    VEC1   :<ARRAY IDENTIFIER>;
            "ARRAY" VEC1[LOW:UPP];
            ENTRY: THE VECTOR TO BE SORTED INTO
                   NONDECREASING ORDER;
            EXIT: THE CONTENTS OF VEC1 ARE LEFT INVARIANT;
    VEC2   :<ARRAY IDENTIFIER>;
            "INTEGER""ARRAY" VEC2[LOW:UPP];
            EXIT: THE PERMUTATION OF INDICES CORRESPONDING TO
                  SORTING THE ELEMENTS OF VEC1 INTO
                  NON-DECREASING ORDER;
    LOW   : <ARITHMETIC EXPRESSION>;
            THE LOWER INDEX OF THE ARRAYS VEC1 AND VEC2;
    UPP   : <ARITHMETIC EXPRESSION>;
            THE UPPER INDEX OF THE ARRAYS VEC1 AND VEC2;

PROCEDURES USED: NONE.

REQUIRED CENTRAL MEMORY: ONE LOCAL INTEGER ARRAY OF
                          LENGTH N,WHERE N = UPP - LOW + 1.

RUNNING TIME: AVERAGE PROPORTIONAL TO N * LN(N).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE: SORTING BY MERGING. ([1],[2])

EXAMPLE OF USE: THE PROCEDURE MERGESORT IS USED IN SYMEIGIMP
                (SECTION 3.3.1.1.3.3).


SUBSECTION: VECPERM.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:

    "PROCEDURE" VECPERM(PERM,LOW,UPP,VECTOR);
    "VALUE" LOW,UPP; "INTEGER" LOW,UPP;
    "INTEGER" "ARRAY" PERM;"ARRAY" VECTOR;
    "CODE" 36404;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    PERM   :<ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" PERM[LOW:UPP];
            ENTRY: A GIVEN PERMUTATION (E.G.AS PRODUCED BY
            MERGESORT) OF THE NUMBERS IN THE ARRAY VECTOR;
    LOW    :<ARITHMETIC EXPRESSION>;
            THE LOWER INDEX OF THE ARRAYS PERM AND VECTOR;
    UPP    :<ARITHMETIC EXPRESSION>;
            THE UPPER INDEX OF THE ARRAYS PERM AND VECTOR;
    VECTOR :<ARRAY IDENTIFIER>;
            "ARRAY" VECTOR[LOW:UPP];
            ENTRY: THE REAL VECTOR TO BE PERMUTED;
            EXIT: THE PERMUTED VECTOR ELEMENTS.

PROCEDURE  USED: NONE.

REQUIRED CENTRAL MEMORY :
    ONE LOCAL BOOLEAN ARRAY OF LENGTH N IS DECLARED.

RUNNING TIME: PROPORTIONAL TO N.

LANGUAGE: ALGOL 60.

EXAMPLE OF USE: THE PROCEDURE VECPERM IS USED IN SYMEIGIMP;
                (SECTION 3.3.1.1.3.3).


SUBSECTION: ROWPERM.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:

    "PROCEDURE" ROWPERM(PERM,LOW,UPP,I,MATRIX);
    "VALUE" LOW,UPP,I;"INTEGER" LOW,UPP,I;
    "INTEGER" "ARRAY" PERM;"ARRAY" MATRIX;
    "CODE" 36403;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    PERM   :<ARRAY IDENTIFIER>;
            "INTEGER" "ARRAY" PERM[LOW:UPP];
            ENTRY: A GIVEN PERMUTATION (E.G. AS PRODUCED BY
            MERGESORT) OF THE NUMBERS IN THE ARRAY VECTOR;
    LOW    :<ARITHMETIC EXPRESSION>;
            THE LOWER INDEX OF THE ARRAY PERM;
    UPP    :<ARITHMETIC EXPRESSION>;
            THE UPPER INDEX OF THE ARRAY PERM;
    I      :<ARITHMETIC EXPRESSION>;
            THE ROW INDEX OF THE MATRIX ELEMENTS;
    MATRIX :<ARRAY IDENTIFIER>:
            "ARRAY" MATRIX [I :I, LOW : UP];
            ENTRY:MATRIX [I, LOW : UP] SHOULD CONTAIN THE
            ELEMENTS TO BE PERMUTED;
            EXIT: MATRIX[I, LOW : UP] CONTAINS THE ROW OF
            PERMUTED ELEMENTS;

PROCEDURES USED: NONE.

REQUIRED CENTRAL MEMORY:
    ONE LOCAL BOOLEAN ARRAY OF LENGTH N IS DECLARED.

RUNNING TIME: PROPORTIONAL TO N, WHERE N = UPP - LOW + 1.

LANGUAGE: ALGOL 60.

EXAMPLE OF USE: THE PROCEDURE ROWPERM IS USED IN SYMEIGIMP.
                (SECTION 3.3.1.1.3.3).

REFERENCES:

    [1]   D.E. KNUTH , THE ART OF COMPUTER PROGRAMMING,
          VOL. 3/ SORTING AND SEARCHING,ADDISON-WESLEY 1973.
          (SECTION 5.2.4  P.159-173).
    [2]   A.V. AHO, J.E. HOPCROFT & J.D. ULLMAN,
          THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS,
          ADDISON-WESLEY 1974.
          (SECTION I.M, P65-67).

SOURCE TEXTS:
"CODE" 36405;
"CODE" 36404;
"CODE" 36403;