How to resolve the algorithm Sorting algorithms/Merge sort step by step in the PL/I programming language

Published on 12 May 2024 09:40 PM
#Pl/i

How to resolve the algorithm Sorting algorithms/Merge sort step by step in the PL/I programming language

Table of Contents

Problem Statement

The   merge sort   is a recursive sort of order   nlog(n). It is notable for having a worst case and average complexity of   O(nlog(n)),   and a best case complexity of   O(n)   (for pre-sorted input). The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements   (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its   divide and conquer   description.

Write a function to sort a collection of integers using the merge sort.

The merge sort algorithm comes in two parts: The functions in pseudocode look like this:

Note:   better performance can be expected if, rather than recursing until   length(m) ≤ 1,   an insertion sort is used for   length(m)   smaller than some threshold larger than   1.   However, this complicates the example code, so it is not shown here.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Merge sort step by step in the PL/I programming language

Source code in the pl/i programming language

MERGE: PROCEDURE (A,LA,B,LB,C);

/* Merge A(1:LA) with B(1:LB), putting the result in C 
   B and C may share the same memory, but not with A.
*/
   DECLARE (A(*),B(*),C(*)) BYADDR POINTER;
   DECLARE (LA,LB) BYVALUE NONASGN FIXED BIN(31);
   DECLARE (I,J,K) FIXED BIN(31);
   DECLARE (SX) CHAR(58) VAR BASED (PX);
   DECLARE (SY) CHAR(58) VAR BASED (PY);
   DECLARE (PX,PY) POINTER;

   I=1; J=1; K=1;
   DO WHILE ((I <= LA) & (J <= LB));
      PX=A(I); PY=B(J);
      IF(SX <= SY) THEN
         DO; C(K)=A(I); K=K+1; I=I+1; END;
      ELSE
         DO; C(K)=B(J); K=K+1; J=J+1; END;
   END;
   DO WHILE (I <= LA);
      C(K)=A(I); I=I+1; K=K+1;
   END;
   RETURN;
END MERGE;

MERGESORT: PROCEDURE (AP,N) RECURSIVE ;

/* Sort the array AP containing N pointers to strings */

     DECLARE (AP(*))              BYADDR POINTER;
     DECLARE (N)                  BYVALUE NONASGN FIXED BINARY(31);
     DECLARE (M,I)                FIXED BINARY;
     DECLARE AMP1(1)              POINTER BASED(PAM);
     DECLARE (pX,pY,PAM) POINTER;
     DECLARE SX CHAR(58) VAR BASED(pX);
     DECLARE SY CHAR(58) VAR BASED(pY);

   IF (N=1) THEN RETURN;
   M = trunc((N+1)/2);
   IF (M>1) THEN CALL MERGESORT(AP,M);
   PAM=ADDR(AP(M+1));
   IF (N-M > 1) THEN CALL MERGESORT(AMP1,N-M);
   pX=AP(M); pY=AP(M+1);
   IF SX <= SY then return;     /* Skip Merge */
   DO I=1 to M; TP(I)=AP(I); END;
   CALL MERGE(TP,M,AMP1,N-M,AP);
   RETURN;
END MERGESORT;

You may also check:How to resolve the algorithm Find the intersection of two lines step by step in the Ada programming language
You may also check:How to resolve the algorithm File size step by step in the Groovy programming language
You may also check:How to resolve the algorithm Compound data type step by step in the Wren programming language
You may also check:How to resolve the algorithm Unprimeable numbers step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Command-line arguments step by step in the BBC BASIC programming language