A5h UT$SORT quicksort routine
Input D register - number of items to be sorted
X register - address of caller supplied routine
Output - none -
Description

Provides the core utility for a Quick Sort. The routine assigns space for a Tag for each of the items to be sorted. The caller's routine is then called for each item to obtain the Tag. These are then sorted, again using the routine at X to supply the comparison routine. Once sorted the Tags are passed in order to the routine at X.

The caller supplied routine is called in three different ways,and should conform to the following spec:

  • if b=0:
         x - number of record (0-n-1)
         leaves
         x:= tag for that record
  • if b=1:
         x - tag for left hand record
         s0 - tag for right hand record
         should leave condition flags as for 'cmp x,s0'
  • and when b=2:
         x - tag for next record in sorted order

Note - The caller supplied routine MUST NOT use utw_r0,r1,r2 or r3 without preserving the EACH time it is called. Nor should this routine use the runtime buffer rtb_bl:rtt_bf since this is used in the sort code at all times.

This call is not available on CM/XP machines.

Example Sorts the qwerty alphabet into order
        LDD     #26
        LDX     #MYROUTINE
        OS      UT$SORT
        BCC     OKRTS
        OS      ER$MESS
OKRTS:  RTS

MYROUTINE:
        TSTB
        BNE     LBL1
        XGDX                    ; returns address of letter
        ADDD    #ORIGINAL
        XGDX
        RTS

LBL1:   DECB
        BNE     LBL2
        LDAA    0,X
        LDX     UTW_S0:
        LDAB    0,x
        CBA                     ; does comparison
        RTS

LBL2:   LDAA    0,X             ; copies sorted letters in order
        LDX     SRTTAG
        STAA    0,X
        INX
        STX     SRTTAG
        RTS

SRTTAG:
        DW      SORTED
ORIGINAL:
        ASCII   "QWERTYUIOPASDFGHJKLZXCVBNM"
SORTED:
        DSZ     26
Errors 254 - either failed to allocate space for the tags or developed too many partitions.