Quicksort

Overview

In this assignment you will read a file of records into a table, then sort the records using the non-recursive Quicksort Algorithm 5.2.2Q found in TAoCP, Vol 3, pp 115-6. After sorting, the records will be printed.

Processing

Your program should be a single assembly with three routines:

A driver routine to
- read the input file and construct a table from the records
- print a short header then call a print routine to print the table
- call the quicksort routine to sort the table by word key (three-digit number)
- print a short header then call a print routine to print the table again
You will need to pass a to each routine standard parameter list consisting of the address of the table and the address of a pointer to the next available entry. Quicksort should calculate N from these.
A print routine to print the table entries
A sort routine implementing non-recursive quicksort (Algorithm 5.2.2Q) to sort the table

Requirements

The file to be sorted is the same one used in Assignment 6:
```
//GO.XREAD DD DSN=T90MES1.C464.DATA(ASN6DATA),DISP=SHR
```
The sorted file should look just like the other file in Assignment 6:
```
//GO.XREAD DD DSN=T90MES1.C464.DATA(ASN6DATB),DISP=SHR
```
Algorithm Q depends on a value called M which you should set to 1. This will eliminate the need to write the insertion sort code in step Q9; in fact, Q9 can be just a label before the standard exit code.
The algorithm requires the use of an auxiliary stack. This should be allocated sequentially with two words in each entry. The stack should be no larger than the algorithm requires for 270 entries.
The algorithm also requires the existence of two "special" keys, one of which is less than all input keys, and one which is larger. You should construct your table so that the first entry (at offset 0) has K(0) = 0, and just after the last record put record R(N+1) with K(N+1) = 999. (Record N+1 will occupy the location pointed to by the NAV pointer.) You might want to choose unique data for these special records so that they are obvious if you accidentaly include them in the result.
The algorithm contains a number of index values: i, j, l, and r (similar to the topological sort), each of which should probably be kept in a register. In fact, you might try using EQU to define these as register symbols, such as i EQU 7. As in Assignment 4, you should write a BASE macro to convert index values to addresses when you need them, although you won't be able to refer directly to the table address, as it is a passed parameter.

Notes

The input data set is:

//GO.XREAD DD DSN=T90MES1.C464.DATA(ASN6DATA),DISP=SHR

As always, document your code using the standards for this course.