; MSORT (MERGESORT)

          INCLUDE IRVINE16.INC

          .DATA

ARRAY	  WORD 13, 24, 32, 56, 47, 63, 44, 35, 26, 73, 32, 53, 28, 77, 23, 42
	  N = ($-ARRAY)/2

LOWHLFTOP WORD ?
UPPHLFTOP WORD ?

          .CODE

MAIN      PROC

          MOV  AX, @DATA
          MOV  DS, AX
          MOV  CX, N
          MOV  SI, OFFSET ARRAY
     L1:  MOV  AX, [SI]
          PUSH AX         ; PUSH ARRAY OF WORDS ONTO STACK
          ADD  SI, 2
          LOOP L1
          MOV  SI, SP
          MOV  BX, N
          CALL MSORT      ; MERGESORT DATA ON STACK
          MOV  CX, N
     L2:  POP  AX         ; POP WORDS AND DISPLAY THEM
          CALL WRITEINT
          CALL CRLF
          LOOP L2
          CALL READINT    ; CHEAP FIX 
          MOV  AX, 4CH
          INT  21H

MAIN      ENDP

MSORT     PROC
          ; RECEIVES
          ;   SI = POINTER INTO STACK WHERE LIST BEGINS
          ;   BX = # WORDS IN LIST
          ; RETURNS WITH LIST SORTED (AND REGISTERS SCRAMBLED)

          CMP  BX, 1
          JG   L1
          RET
     L1:  MOV  BP, SI
          MOV  CX, BX

     L2:  MOV  AX, [BP] ; COPY ORIGINAL LIST ONTO STACK AGAIN
          PUSH AX
          ADD  BP, 2
          LOOP L2

          MOV  AX, SP
          PUSH SI       ; SAVE SI AND BX FOR AFTER NEXT MSORT CALL
          PUSH BX

          MOV  SI, AX   ; SI = BASE OF LOWER 1/2 LIST
          SHR  BX, 1    ; BX = # WORDS IN 1/2 LIST
          CALL MSORT    ; NOW SORT LOWER 1/2 LIST

          POP  BX       ; RESTORE SI AND BX
          POP  SI
          MOV  AX, SP
          ADD  AX, BX   ; BX = # WORDS IN LIST = # BYTES IN 1/2 LIST
          PUSH SI       ; AGAIN SAVE SI AND BX FOR AFTER NEXT MSORT CALL
          PUSH BX

          MOV  SI, AX   ; SI = BASE OF UPPER 1/2 LIST
          SHR  BX, 1    ; BX = # WORDS IN 1/2 LIST
          CALL MSORT    ; NOW SORT UPPER 1/2 LIST

          POP  BX       ; RESTORE SI AND BX
          POP  SI

          ; BOTH HALVES ARE NOW SORTED, SO NOW MERGE THEM. BUT THERE'S A TECHNICAL PROBLEM:
          ; ONLY SP AND BP CAN BE USED TO INDIRECTLY ACCESS THE STACK, SO WATCH....

          MOV  CX, BX   ; PREP COUNTER FOR MERGING LOOP
          MOV  DX, SP   ; DX WILL HOLD POINTER INTO LOWER 1/2 LIST
          MOV  DI, SP
          ADD  DI, BX   ; DI WILL HOLD POINTER INTO UPPER 1/2 LIST
          MOV  AX, DI
          MOV  LOWHLFTOP, AX  ; REMEMBER TOO FAR FOR LOWER 1/2 LIST
          ADD  AX, BX
          MOV  UPPHLFTOP, AX  ; REMEMBER TOO FAR FOR UPPER 1/2 LIST

     L3:  CMP  DX, LOWHLFTOP
          JE   L4       ; SKIP AHEAD IF DONE WITH LOWER 1/2 LIST
          CMP  DI, UPPHLFTOP
          JE   L5       ; SKIP AHEAD IF DONE WITH UPPER 1/2 LIST
          MOV  BP, DX   ; OTHERWISE, GET WORD FROM LOWER 1/2
          MOV  AX, [BP]
          MOV  BP, DI   ; COMPARE WITH WORD FROM UPPER 1/2
          CMP  AX, [BP]
          JL   L5       ; SKIP AHEAD IF LOWER 1/2 WORD IS SMALLER
     L4:  MOV  BP, DI
          MOV  AX, [BP] ; TAKE FROM UPPER 1/2 LIST (IF SMALLER)
          ADD  DI, 2    ; ADVANCE UPPER 1/2 POINTER
          JMP  L6
     L5:  MOV  BP, DX
          MOV  AX, [BP] ; TAKE FROM LOWER 1/2 LIST (IF SMALLER)
          ADD  DX, 2    ; ADVANCE LOWER 1/2 POINTER
     L6:  MOV  BP, SI   ; PUT SMALLER OF THE TWO WORDS INTO ORIGINAL LIST
          MOV  [BP], AX
          ADD  SI, 2    ; ADVANCE POINTER FOR ORIGINAL LIST
          LOOP L3

          MOV  AX, BX   ; FIX SP BEFORE RETURNING
          SHL  AX, 1
          ADD  AX, SP
          MOV  SP, AX
          RET

MSORT     ENDP

END       MAIN