BCL Molecular Disc Sort Utility

This overlay module enables an application program (running as a printer task) to sort up to 65,535 records into any required sequence. The task proceeds through three phases: Scan, Sort and (optionally) Print.

SCAN Phase

The database is examined and one record is written to a Direct Access "Sort Work File" for each item to be included in the sort. The count of records written (which may be zero) is placed into the first word of the File Status Block. This phase is custom written by the application programmer.

The Work File record length is 8 words the first of which is reserved for system use and the remaining 7 are the Sort Key (which must include the means to identify the item).

The Sort Key is an unsigned 119-bit value comprising any ASCII, Metacode or Binary Subfields in any sequence. Where a Binary Subfield may contain 2s-complement negative values it is mathematically necessary to complement its sign bit.

SORT Phase

The Work File is sorted into ascending Key sequence by the Sort Utility Module entirely within the 2K-task partition using an 8-sector disc buffer:

JSBR IZ 1670   FETCH & LINK Overlay
P1=002002
P2=0/0225      -> Sort Module Number
P3=000210      B17=no messages, B16:B1=Sort Work File Id
P4=            ->Follow-on Print Program Name

Sort start and done messages will be flashed to the task identified in step 3400- unless P3 bit 17 is set. On completion of sort the follow-on program is given control, or the utility will JUMP Z 1402 if this is not found in the printer directory. All task memory below 3200- is modified during the Sort phase.

The records are sorted using the "Quick Sort" algorithm: an arbitrary "pivot" key is chosen from the file and the file is split into "high" and "low" partitions (relative to the pivot) by comparing the pivot with each other key and swapping where necessary, thus the pivot ends in its correct position. This process is then applied recursively on each partition, however any partition with less than 20 records is sorted in-memory using the "Bubble Sort" algorithm. (M18 source code)

PRINT Phase (optional)

The Work File is read in descending (or ascending) sequence to obtain the identification of the next print item. This phase is also custom written by the application programmer.

Exclusivity

It may be necessary to prevent two tasks attempting to use the same Sort Work File simultaneously. This may be handled either by a semaphore in the FSB or by allocating a separate work file to each printer task.

Timing Guide

A dedicated M18 Mk4 with Hawk Drive under LOS scanned 20,000 64-word product records, writing 14,019 records to the Sort Work File, in 78 seconds. The Work File was sorted in 234 seconds.

To achieve this speed in the Scan phase it is essential to avoid FETCH and OVERWRITE by using JSBR IZ 1615 "Transfer" with an 8 sector read buffer and 4 sector write buffer (coding example available).

Installation

Click here to download the Sort Module mod025.ZIP (1K).

  1. Move Sort Module into Overlay library preferably as Module Number 025.
  2. Add SORT work file(s) as required to System Catalogue, File Table and FE utility preferably as File Id 210. Each work file must have:
    • Record Length = 8 words
    • Minimum Record Number = 1
    • Maximum Record Number = multiple of 64
    • Shared Buffer, size 1 or more sectors
    • File Status Block of 1 word (2 words if semaphore required)
  3. Reboot.