; Quicksort procedure - Adapted from C++ to Assembly.  Original algorithm was taken from
    ; programs 7.1 and 7.2 of "Algorithms in C++" by Robert Sedgewick.
    ; This procedure sorts the array called "myArray", from position si to position di.
    ; To call it, place the index of the first number to be sorted in si and the index of
    ; the last number to be sorted in di, then call quicksort.
    ; This quicksort uses the first element of the subarray as the pivot, which is extremely
    ; bad for nearly-sorted lists.  Also, insertion sort may have been better for a small list
    ; as the program required.  But it seemed that quicksort would be a more useful procedure
    ; to have around for later programs
    quicksort proc
        cmp si,di			; The base case is an array of one or fewer elements
        jae done			; In this case, si = di.  Do nothing and return

        jmp continue			; Jump over "done" and continue with quicksort


      done:				; Done label
        ret				; Return

      continue:				; Quicksort
	mov al, myArray[di]		; Store the last element in al to use as the pivot
	mov first, si			; Store si in first
	mov last, di			; Store di in last
	dec si				; Decrement si to one less than first

       ; Move through the array from left to right until finding an element
       ; that is greater than the pivot
       moveLeftSide:
         inc si				; Increment si. The first time through, this sets si to the first element again
         cmp myArray[si], al		; If myArray[si] is less than to the pivot,
         jb moveLeftSide		; Keep looking


       ; Move through the array from right to left until finding an element
       ; that is less than the pivot
       moveRightSide:
	 dec di				; Decrement di (move left)
	 cmp di,first			; To prevent "falling off" the left end of the array,
	 je swapIt			; once di == first, stop looking (go to swapIt)

	 cmp myArray[di], al		; If myArray[si] is greater than the pivot
	 ja MoveRightSide		; keep looking

	 cmp si, di			; If si "passes" di, then the partitioning step is done
	 jae swapIt			; Go to swapIt and put the pivot in its final position

	 ; After finding two elements that are in the "wrong" side, switch them
	 mov ch, myArray[di]		; Put DI in ch (temp variable)
	 mov cl, myArray[si]		; Put SI in cl (temp variable)
	 mov myArray[di], cl		; Move cl (what was SI) into DI
	 mov myArray[si], ch		; Move ch (what was DI) into SI

	 ; Continue the partitioning step indefinitely until conditions in the above code end the loop
	 jmp moveLeftSide

	 ; Once the list has been divided into a less-than-pivot half and a greater-than-pivot
	 ; half, the pivot can be put into it's permanent place, which is between the two halves.
	 ; Switch the pivot with the first element greater than the pivot, which is in myArray[si]
       swapIt:

	 mov di, last			; Move last back into di to get position of the pivot
	 mov ch, myArray[si]		; Use ch and cl again as temporary variables
	 mov cl, myArray[di]		; to switch the pivot myArray[di] into
	 mov myArray[si], cl		; its final position, which will be at
	 mov myArray[di], ch		; myArray[si]

	 mov pivotIndex, si		; Store the position of the pivot in pivotIndex
	 mov si, first			; Move first into si
	 mov di, last			; Move last into di
	 mov ax, pivotIndex		; Move the pivotIndex into ax

	 push si			; Push SI, DI and AX onto the stack to save
	 push di			; them across the resursive call
	 push ax			; to quicksort

	 mov di, ax			; The first recursive call will begin at first (already in SI)
	 dec di				; and end at 1 position before the pivot (which is already in place)
	 call quicksort			; Call quicksort to recursively sort the left half of the list

	 pop ax				; Restore the values of SI, DI and AX
	 pop di				; in reverse order of the order they were placed on the stack
	 pop si				; to get back the first and last positions and the position of the pivot

	 mov si, ax			; The second recursive call will begin at 1 position after the pivot,
	 inc si				; and end at the last position (which is already in DI)
	 call quicksort			; Call quicksort to recursively sort the right half of the list

	 ret				; Return

    quicksort endp

cmp di, 0
jl <address offset>