name    qsorti
        title   QSORTI.ASM Integer QuickSort
        page    55,132
;
; QSORTI.ASM --- Integer Quicksort
;
; Copyright 1988, Ziff Communications Co.
; PC Magazine * Ray Duncan
;
; Call with:    DS:SI = address of first item to sort
;               DS:DI = address of last item to sort
;               Assumes items are 2-byte integers
;
; Returns:      Nothing, all registers unchanged.
;

itemsiz equ     2               ; bytes per integer

_TEXT   segment word public 'CODE'

        assume  cs:_TEXT,ds:NOTHING,es:NOTHING

                                ; stack variables       
left    equ     [bp-8]          ; first item to sort
right   equ     [bp-4]          ; last item to sort

        public  qsorti          ; make visible to Linker

qsorti  proc    near

        cmp     di,si           ; if right <= left
        jna     qsort5          ; just exit

        push    bp              ; set up stack frame
        mov     bp,sp           ; and local variables
        push    es              
        push    di              ; offset last item
        push    ds
        push    si              ; offset first item
        push    dx
        push    cx
        push    bx
        push    ax      
        
        sub     si,itemsiz      ; SI = i = left - 1
                                ; DI = j = right
        mov     bx,di           ; BX = right

qsort1:                         ; partition array on
                                ; value of rightmost item

qsort2:                         ; scan right for item
                                ; >= partitioning value

        add     si,itemsiz      ; i++

        mov     ax,[si]         ; while(items[i] < items[right])
        cmp     ax,[bx]         ; (guaranteed to terminate
        jl      qsort2          ;  when i = right)

qsort3:                         ; scan left for item
                                ; <= partitioning value

        sub     di,itemsiz      ; j--

        cmp     di,left         ; while(items[j] > items[right]
        jna     qsort4          ; && (j > left)
        mov     ax,[di]
        cmp     ax,[bx]
        jg      qsort3

qsort4: mov     ax,[di]         ; exchange the items
        xchg    ax,[si]
        mov     [di],ax

        cmp     di,si           ; while(j > i)
        ja      qsort1          ; (do until pointers cross)

        mov     ax,[di]         ; undo the last exchange
        xchg    ax,[si]
        mov     [di],ax

        mov     ax,[bx]         ; put the partitioning
        xchg    ax,[si]         ; element into position
        mov     [bx],ax

        push    si              ; save i

        mov     di,si           ; qsort(left, i-1)
        sub     di,itemsiz
        mov     si,left
        call    qsorti
        
        pop     si              ; qsort(i+1, right)
        add     si,itemsiz
        mov     di,right
        call    qsorti

        pop     ax              ; restore registers,
        pop     bx              ; discard stack frame
        pop     cx
        pop     dx
        pop     si
        pop     ds
        pop     di
        pop     es
        pop     bp

qsort5: ret                     ; return to caller

qsorti  endp

_TEXT   ends

        end