TITLE    Sorting an array by insertion sort    INS_SORT.ASM
COMMENT |
        Objective: To sort an integer array using insertion sort.
            Input: Requests numbers to fill array.
|          Output: Displays sorted array.
.MODEL SMALL
.STACK 100H
.DATA
MAX_SIZE       EQU 100
array          DW  MAX_SIZE DUP (?)
input_prompt   DB  'Please enter input array: '
               DB  '(negative number terminates input)',0
out_msg        DB  'The sorted array is:',0

.CODE
.486
INCLUDE io.mac
main    PROC
        .STARTUP
        PutStr  input_prompt ; request input array
        mov     BX,OFFSET array
        mov     CX,MAX_SIZE
array_loop:
        GetInt  AX           ; read an array number
        nwln
        cmp     AX,0         ; negative number?
        jl      exit_loop    ; if so, stop reading numbers
        mov     [BX],AX      ; otherwise, copy into array
        add     BX,2         ; increment array address
        loop    array_loop   ; iterates a maximum of MAX_SIZE
exit_loop:
        mov     DX,BX        ; DX keeps the actual array size
        sub     DX,OFFSET array  ; DX := array size in bytes
        shr     DX,1         ; divide by 2 to get array size
        push    DX           ; push array size & array pointer
        push    OFFSET array
        call    insertion_sort
        PutStr  out_msg      ; display sorted array
        nwln
        mov     CX,DX
        mov     BX,OFFSET array
display_loop:
        PutInt  [BX]
        nwln
        add     BX,2
        loop    display_loop
done:                        
        .EXIT
main    ENDP

;-----------------------------------------------------------
; This procedure receives a pointer to an array of integers
; and the array size via the stack. The array is sorted by
; using insertion sort. All registers are preserved.
;-----------------------------------------------------------
SORT_ARRAY  EQU  [BX]
insertion_sort PROC
       pusha                 ; save registers
       mov     BP,SP
       mov     BX,[BP+18]    ; copy array pointer
       mov     CX,[BP+20]    ; copy array size
       mov     SI,2          ; array left of SI is sorted
for_loop:
       ; variables of the algorithm are mapped as follws:
       ; DX = temp, SI = i, and DI = j
       mov     DX,SORT_ARRAY[SI] ; temp := array[i]
       mov     DI,SI         ; j := i-1
       sub     DI,2
while_loop:
       cmp     DX,SORT_ARRAY[DI]  ; temp < array[j]
       jge     exit_while_loop
       ; array[j+1] := array[j]
       mov     AX,SORT_ARRAY[DI]
       mov     SORT_ARRAY[DI+2],AX
       sub     DI,2          ; j := j-1
       cmp     DI,0          ; j >= 0
       jge     while_loop
exit_while_loop:
       ; array[j+1] := temp
       mov     SORT_ARRAY[DI+2],DX
       add     SI,2          ; i := i+1
       dec     CX
       cmp     CX,1          ; if CX = 1, we are done
       jne     for_loop
sort_done:
       popa                  ; restore registers
       ret     4
insertion_sort ENDP
       END     main