# Quick Sort in x86 assembly (MASM)

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)
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.

• Is the array-to-be-sorted supposed to be hardcoded in or were you supposed to take user input?
– Mast
Apr 7, 2018 at 9:45
• Let me give you a thought experiment: What would happen if you commented out the push edx, mov edx, [ebp + 16], and pop edx from _partition@12? Passing parameters on the stack is a common way to call functions, and there are benefits to using a known and understood parameter passing protocol. But it's not the only way, or even the fastest. For a pure asm program (such as this), passing (some of) the parameters in registers might be useful. Apr 7, 2018 at 12:59
• @ David Wohlferd If i didn't use edx, I would have to read [ebp + 16] from memory for every iteration of the loop L2, which is supposed to be slow. The rational is that it's better to read it from memory just once into a register. Apr 7, 2018 at 14:53
• @ Mast We are not given the initial array to be sorted, and I don't know how to generate an array of random integers in assembly, so I just hardcoded one. There is some I/O but I left that out because it was too much code to post here. Apr 7, 2018 at 14:58

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.

• @ Regiter use. I've been choosing registers almost arbitrarily! LOL it seems like a bit too much fuss to worry about what roles each reg is supposed to play. I see what you mean about ecx (p), though. It could have been the counter instead of assigning it's value to another counter variable. I didn't notice that. : ) Apr 7, 2018 at 23:08
• @ EAX in _quicksort. Wow! That's a huge bug I didn't notice. But mysteriously, it works. For the past 30 minutes I've been trying to figure out why the program works. lol I think it's because _quicksort first sets the value of eax (with it's partition call) before it uses it to make other calls. The result is that it's not affected by any changes to eax made by the calling function, and in turn, it doesn't have any affect on it's calls to itself - the net result, nothing changes, no bug. It worked out without having to fix it. lol. I'll save and restore eax anyway to stick to convention. Apr 7, 2018 at 23:23
• @Calling covention in partition. This is a good point, i never thought of that. We're supposed to stick to std_call convention, but you're right. If it's a subroutine that's only used by this function, there's no reason to stick to any specific convention. No need to even bother with a stack frame. Good observation. Apr 7, 2018 at 23:34
• @Duplicate coditional jmp. Hmmm. This never crossed my mind cause that's not even possible in the control structures in high level languages. That's like a combination of while and do-while. But is saving a jump instruction really more efficient than duplicating cmp instructions? Apr 7, 2018 at 23:49