For the final part of this series on the PL/I programming language as implemented on MTS, let's implement radix sort from Rosetta Stone.

## The problem

Radix sort is intended as a fast way to sort an array of integers by grouping them by digits that share the same value. Digits can be defined depending on the numeric base and the sort can take place from either the most significant digit or the least. Here we'll sort by most significant digit and use base 2. so we are comparing by bits.

The algorithm we'll use sorts in place. Starting at the largest bit it will group the numbers into one range where the bit is 1 and another where it is 0 by swapping values in the array. It will then recursively sort each range by the next smallest bit.

## The solution

Here's how the implementation looks; this was based on the C version at Rosetta Code.

``````RADIX_SORT: PROCEDURE(FROM, TO, BIT, ARR) RECURSIVE;
DECLARE (FROM, TO) FIXED DECIMAL;
DECLARE BIT FIXED BINARY(16);
DECLARE ARR(*) FIXED BINARY(16);

DECLARE (LEFT, RIGHT) FIXED DECIMAL;
DECLARE TEMP FIXED BINARY(16);

/* Exit early if bit down to zero or range is zero */
IF (BIT = 0) | (TO <= FROM) THEN RETURN;

LEFT = FROM;
RIGHT = TO;

LOOP:
/* Find the leftmost with the bit set */
DO WHILE ((LEFT < RIGHT) & ((ARR(LEFT) & BIT) = 0));
LEFT = LEFT + 1;
END;

/* Find the rightmost with the bit not set */
DO WHILE ((LEFT < RIGHT) & ((ARR(RIGHT) & BIT) ¬= 0));
RIGHT = RIGHT - 1;
END;

/* If found one of each, swap and loop again to look for more */
IF LEFT < RIGHT THEN BEGIN;
TEMP = ARR(LEFT);
ARR(LEFT) = ARR(RIGHT);
ARR(RIGHT) = TEMP;
GO TO LOOP;
END;

/* If nothing found, make the first sub search do the full range */
IF ((BIT & ARR(LEFT)) = 0) & (LEFT <= TO) THEN
LEFT = LEFT + 1;

/* The two ranges bounded by LEFT are now sorted by BIT.
* Sort each range by the next least significant bit */
BIT = BIT / 2;
``````

The definition of the function is marked as `RECURSIVE`, similar to other languages like ALGOL, as otherwise calling the function from itself will not work.

We pass in an array of fixed point numbers of up to 16 bits in length with the dimensions of the array bounded by `FROM` and `TO`. The initial call will set `BIT` to be 2^15. To handle an array of any size we can use `*` in the declaration `DECLARE ARR(*) FIXED BINARY(16);`.

Although PL/I has logical operators - and is `&`, or is `|`, not is `¬` - it does not seem to have the boolean not operator like `!` in C, so we have to write `(ARR(LEFT) & BIT) = 0` rather than something like `! (ARR(LEFT) & BIT)`.

We'll also need a procedure to print the array which will be called before and after the sort.

``````SHOW_ARR: PROCEDURE(LABEL, ARR);
DECLARE LABEL CHARACTER(80) VARYING;
DECLARE ARR(*) FIXED BINARY(16);
PUT FILE (SCARDS) LIST(LABEL);
PUT FILE (SCARDS) SKIP;
PUT FILE (SCARDS) LIST(ARR);
PUT FILE (SCARDS) SKIP;
END SHOW_ARR;
``````

Finally, we set up the main function

``````TEST: PROCEDURE OPTIONS(MAIN);
DECLARE RADIX_SORT ENTRY (FIXED DECIMAL, FIXED DECIMAL,
FIXED BINARY(16),);

DECLARE NUMS(10) FIXED BINARY(16);
NUMS(1) = 3;       NUMS(6) = 1630;
NUMS(2) = 42;      NUMS(7) = 4;
NUMS(3) = 910;     NUMS(8) = 2721;
NUMS(4) = 3241;    NUMS(9) = 684;
NUMS(5) = 99;      NUMS(10) = 11;

CALL SHOW_ARR('Before', NUMS);
CALL SHOW_ARR('After', NUMS);

END TEST;
``````

Note that we need to declare the signature of RADIX_SORT before we use it.

We can now compile and run the program.

``````# \$run *pl1f scards=radix.pl1 spunch=-load
# Execution begins   20:03:01

PROCEDURE TEST: SYNTAX CHECK COMPLETED. COMPILATION CONTINUES.

NO ERRORS OR WARNINGS DETECTED.
# Execution terminated   20:03:02  T=0.128

# Execution begins   20:03:03
'Before'
3        42       910      3241        99      1630         4      2721
684        11
'After'
3         4        11        42        99       684       910      1630
2721      3241

# Execution terminated   20:03:03  T=0.003
``````