Quick Sort in x86 assembly (MASM)

Question

My task was to implement Quick Sort in assembly from pseudocode.

;*******************************************************************************
; This program implements the Quick Sort algorithm and sorts an array
;
; Author: William 
; Date: 4/6/18

                TITLE   Quick Sort      
                .386 
                .model  flat, stdcall
                .stack  4096

; prototype from Kernel32 lib
ExitProcess     PROTO, dwExitCode:DWORD 

.data

; An array of 25 random integers to be sorted
array           DWORD   43, 91, 97, 63, 52,
                        58, 99, 19, 33, 26,
                        77, 11, 41, 89, 27,
                        99, 98, 68, 26,  5,
                        73, 47, 46, 59, 21 

.code

;-------------------------------------------------------------------------------
; _partition@12 (A , p, r)
;
; Quicksort subroutine
;
; Entry: A @ ebp + 8            ; pointer to array being sorted
;        p @ ebp + 12           ; integer index to start of sub-array
;        r @ ebp + 16           ; integer index to end of sub-array 
; 
; Local: x                      ; The pivot 
;        i                      ; index of smaller element
;
; Exit: the index of the pivot stored in eax
;-------------------------------------------------------------------------------
_partition@12:
                ; set up stack, save regs
                push    ebp
                mov     ebp, esp
                push    ebx
                push    ecx
                push    edx
                push    esi
                push    edi

; Load function parameters into registers and initialize local variables
                mov     ebx, [ebp + 8]          ; A stored in ebx
                mov     ecx, [ebp + 12]         ; p stored in ecx
                mov     edx, [ebp + 16]         ; r stored in edx
                mov     esi, [ebx + edx * 4]    ; x initialized to A[r] 
                lea     edi, [ecx - 1]          ; i initialized to p - 1

                ; Loop from index p to r - 1
                mov     eax, ecx                ; j (loop count) initialized to p
L2:             cmp     eax, edx
                jnl     endL2

                ; If A[j] <= x
                cmp     [ebx + eax * 4], esi
                jnle    endIf1
                inc     edi                     ; i = i + 1

                ; swap A[i] with A[j]
                mov     ecx, [ebx + edi * 4]
                xchg    ecx, [ebx + eax * 4]
                mov     [ebx + edi * 4], ecx
endIf1:
                inc     eax
                jmp     L2
endL2:
                ; swap A[i + 1] with A[r]
                inc     edi                     ; i = i + 1
                mov     ecx, [ebx + edi * 4]
                xchg    ecx, [ebx + edx * 4]
                mov     [ebx + edi * 4], ecx

                mov     eax, edi                ; return i + 1

                ; clean up stack, restore regs
                pop     edi
                pop     esi
                pop     edx
                pop     ecx
                pop     ebx
                pop     ebp
                ret     12

;-------------------------------------------------------------------------------
; _quickSort@12 (A , p, r)
;
; Sorts array of DWORD integers
;
; Entry: A @ ebp + 8            ; pointer to array to being sorted
;        p @ ebp + 12           ; integer index to start of sub-array
;        r @ ebp + 16           ; integer index to end of sub-array 
; 
;-------------------------------------------------------------------------------
_quickSort@12:
                ; set up stack, save regs
                push    ebp
                mov     ebp, esp
                push    ebx
                push    ecx
                push    edx

                ; Load function parameters into registers
                mov     ebx, [ebp + 8]          ; A stored in ebx
                mov     ecx, [ebp + 12]         ; p stored in ecx
                mov     edx, [ebp + 16]         ; r stored in edx

                ; if (p < r)
                cmp     ecx, edx
                jnl     endIf2

                ;q = Partition(A, p, r) 
                push    edx
                push    ecx
                push    ebx
                call    _partition@12           ; q stored in eax

                ;Quicksort(A, p, q - 1)
                dec     eax
                push    eax
                push    ecx
                push    ebx
                call    _quickSort@12

                ;Quicksort(A, q + 1, r)
                add     eax, 2
                push    edx
                push    eax
                push    ebx     
                call    _quickSort@12
endIf2:
                ; clean up stack, restore regs
                pop     edx
                pop     ecx
                pop     ebx
                pop     ebp
                ret     12

main:
                push    24
                push    0
                push    OFFSET array
                call    _quickSort@12

                ; array is sorted, but code does not
                ; print it to the console

                INVOKE  ExitProcess, 0
                END     main

This was the pseudocode I used:

Partition(A, p, r)
x = A[r]
i = p - 1 
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

Quicksort(A, p, r)
if p < r
    q = Partition(A, p, r)
    Quicksort(A, p, q - 1)
    Quicksort(A, q + 1, r)

I took the advice given to me on my last post and loaded all function parameters into registers instead of reading and writing to memory over and over. All criticism is appreciated.

Answer 1

This is just a review of the code; I have not verified that the assembly code correctly implements the algorithm in the pseudocode.

Your use of some of the registers is a bit atypical. EAX is typically used as a temporary register or accumulator (so much so that some operations on it have shorter encodings than if those same operations are done with other registers). In your "swap" code, this would normally use EAX instead of ECX. You're using EAX as a count, but you start it off by copying the value from ECX. So just use ECX as the count, and EAX to cycle temporary values thru.

Which leads to my next point: when you make your recursive _quickSort calls, you assume that the value in EAX will not change during the first call, but it can since you're not saving and restoring the value during the call. This will make the second call work on the wrong bounds, resulting in either a longer execution (by sorting a larger area than necessary) or incorrect results (if the full area isn't sorted).

Since _partition is only used locally, it could be given a non-mangled name and parameters passed directly in the registers, rather than using the stack. (The same applies to _quickSort, but if you're going to use this code in a later project, or call it from another language, you might want to keep the passing of parameters on the stack.)

At the end of your while loop (between the endIf1 and endL2 labels), rather than unconditionally jumping to the top of the loop and checking the condition, check the condition and conditionally jump back to the top of the loop. This duplicates the condition check, but avoids an extra jump when the loop terminates. It is also a common optimization in some compiled languages (specifically C and C++).

Your use of negative conditions in conditional jump instructions is (for me) harder to read than the equivalent positive ones. JNL (jump not less) is the same as JGE (jump greater or equal), and JNLE (jump not less or equal) equal to JG (jump greater). Nothing wrong with what you have, but I'm used to the positive versions. Just stay consistent with your usage.