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.

• Mast: Is the array-to-be-sorted supposed to be hardcoded in or were you supposed to take user input?
• David Wohlferd: 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.
• William: @ 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.
• William: @ 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.

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.

• William: @ 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. : )
• William: @ 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.
• William: @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.
• William: @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?