# Quicksort implementation in TASM assembly

Is this assembly (TASM) implementation of quicksort efficient, and does this code follow common best practices?

IDEAL
MODEL small
STACK 100h
DATASEG
; --------------------------
; --------------------------
arr db 3,1,2
var db ?
CODESEG
proc Swap
;swap two values
;1,2 values to be swaped
push bp
mov bp,sp
push di
push bx
push ax
push cx
xor ax,ax
xor cx,cx
mov bx,[bp+6];value to be swapped
mov di,[bp+4];
mov ah,[bx]
mov ch,[di]
mov [bx],ch
mov [di], ah
pop cx
pop ax
pop bx
pop di
pop bp
ret
endp Swap
proc Split
;sorting the array by valus greater then the pivot and values lower then the pivot
;1. start of the array
;2.end of the array
;3. pivot
push bp
mov bp,sp
push ax
push bx
push cx
push dx
push di
mov bx,[bp+8];start of the array(offset)
mov di,[bp+6]; end of the array(offset)
mov ax,[bp+4];pivot
push di ;offset to be swapped
push ax ;offset to be swapped
call Swap
mov ax,bx
mov cx,di
sub cx,bx
inc cx
lpivot:
mov dh,[byte ptr bx]
cmp dh,[byte ptr di]
jae greater
push ax;offset to be swapped
push bx;offset to be swapped
call Swap
inc ax
greater:
inc bx
loop lpivot
push ax;offset to be swapped
push di;offset to be swapped
call Swap
mov [bp+6],ax
pop di
pop dx
pop cx
pop bx
pop ax
pop bp
ret 2
endp Split
proc QuickSort
;sort an array(quicksort implention) usually around O(n log n) complexiy worst case O(n^2)
;1.strat of the array(offset)
;2.end of the array (offset)
push bp
mov bp,sp
push ax
push bx
push cx
push di
mov bx,[bp+6];start of the array(offset)
mov di,[bp+4];end of the array(offset)
cmp bx,di
jae return ;if the array size is 1 or 0 return
push bx;start of the array(offset)
push di;end of the array(offset)
call PickPivot
pop ax;pivot
push bx;start of the array(offset)
push di;end of the array(offset)
push ax;push pivot
call Split
pop ax;new pivot
push bx;start of the array(offset)
dec ax
push ax
call QuickSort
inc ax
inc ax
push ax
push di
call QuickSort
return:
pop di
pop cx
pop bx
pop ax
pop bp
ret
endp QuickSort
proc PickPivot
;1.strat of the array(offset)
;2.end of the array (offset)
push bp
mov bp,sp
push bx
push di
mov bx,[bp+6];start of the array(offset)
mov di,[bp+4];end of the array(offset)
shr bx,1
mov [bp+6],bx
pop di
pop bx
pop bp
ret 2
endp PickPivot
start:
mov ax, @data
mov ds, ax
xor ax,ax
mov bx,offset arr
mov di,offset var
dec di
push bx
push di
call QuickSort
exit:
mov ax, 4c00h
int 21h
END start


This may seem silly to you, after all, you know exactly what the code does. It's obvious, isn't it? But 6 weeks from now or 6 months from now, even 6 years from now, will it still be obvious to you what this code does? And that's just you, the person who wrote it. Reading someone else's assembler is always a challenge.

You are asking for a code review, and I would never sign off on code (assembler or otherwise) that didn't have decent comments describing what it does. If nothing else, performing that last pass thru the code describing what everything does sometimes turns up bugs or inefficiencies.

I realize this may just be a class project, or even just written for your own interest/education. But it's a habit you should acquire. Your future self (and the people you ask to read your code) will thank you.

So, let's start at the top with some file-scope comments. Perhaps something like this:

; qs.asm - Routine to perform a quicksort on a hard-coded
;          list of numbers.
;
; Written for 16bit on i386.
;
; The list of numbers to sort is stored in the variable arr.


And looking at your first procedure, perhaps something like this:

; Swap - swap 2 variables in a list
;
; On input:
; sp + 4 - Pointer to first entry to swap
; sp + 2 - Pointer to second entry to swap
;
; On output:
; nothing
;
; Registers clobbered
; none

proc Swap

push bp     ; Create stack frame
mov bp, sp

push di     ; Preserve all used registers
push bx
push ax
push cx

xor ax, ax   ; Zero register (not sure why you do this?)
xor cx, cx

mov bx, [bp+6]   ; Get pointer to first entry
mov di, [bp+4]   ; Get pointer to second entry

mov ah, [bx]     ; Read first value
mov ch, [di]     ; Read second value

mov [bx], ch     ; Write second value to first location
mov [di], ah     ; Write first value to second location

pop cx     ; Restore used registers
pop ax
pop bx
pop di

pop bp     ; Restore stack
ret

endp Swap


This is the same code as you posted above, just with comments and spacing. It makes the code drastically easier to understand and follow. And it's not like it makes the .exe file any bigger. It also highlights one of those inefficiencies I mentioned (why are you zeroing ax and cx?).

There are several other changes I would make to this routine.

1. You do standard stack-frame code (push bp mov bp, sp), but why? There is no benefit to doing this here, and it will make (what is likely to be) the busiest part of your code that much slower.
2. Using xchg, you can use 1 fewer register.
3. Your routine uses pascal (or cdecl) calling convention (who pops the registers that are passed to Swap?). There is nothing 'wrong' with calling functions this way, but there are alternatives. If you wanted to, you could follow the 'fastcall' convention, which passes parameters in registers instead of on the stack. Not having to read/write memory is typically faster, and requires fewer instructions (which is also faster). The fastcall rules also allow you to use ax without having to preserve it (since it's intended to be the return value). The downside is that if you call a routine that uses this convention, you need to make sure you don't mind having it stomp on the values of any of these registers.

I don't have a 16bit environment to test this, but given the comments, I expect you'll understand the intent, even if I muck up the syntax somewhere.

Implementing 1 & 2:

proc Swap

push ax     ; Preserve all used registers
push bx
push cx

mov bx, [sp+4]   ; Get pointer to first entry
mov cx, [sp+2]   ; Get pointer to second entry

mov al, [bx]     ; Read first value
xchg [cx], al    ; xchg first value and second value
mov [bx], al     ; Write second value back to first location

pop cx     ; Restore used registers
pop bx
pop ax

ret

endp Swap


Note that xchg doesn't allow you to use 2 memory addresses, so you still need ax. But this still uses fewer registers, so needs fewer push/pops.

How about implementing #3? Instead of pushing the two pointers to be swapped onto the stack, what if we pass them in cx and dx? This is the normal 'fastcall' method on 32bit (IIRC, the standard for 16bit was a bit different). Likewise, ax is used to return the 'result.' In our case, there is no result, so we can use the register however we want.

Is changing the way functions are called kosher? Well... kinda. Assembler allows you to pass parameters however you want (as long as both the 'caller' and the 'callee' agree upon the rules), and the CPU certainly isn't going to care. On the other hand, if every routine you write uses a different method, it's going to make reading your code a nightmare (even with comments).

Generally what you want to do is pick 1 standard and use it for most or all of your code. Picking one of the industry standards makes sense. Obviously if your code needs to be callable from C, you must pick a standard that C supports. But since your entire program is asm, that doesn't apply here.

In this example, I'm using the Microsoft Fastcall standard for 32bit code. It's one I'm familiar with (although most of my recent code is 64bit). Obviously before you can use this, you'd need to change the code that calls Swap.

So, that gives us:

; Swap - swap 2 variables in a list
;
; On input:
; cx - Pointer to first entry to swap
; dx - Pointer to second entry to swap
;
; On output:
; nothing
;
; Registers clobbered
; ax

proc Swap

mov al, [cx]     ; Read first value
xchg [dx], al    ; xchg first value and second value
mov [cx], al     ; Write second value back to first location

ret

endp Swap


You know what? The code is getting pretty small here. In fact, does it still make sense to have a routine for this? Or should you just put this code in Split? Putting this code 'inline' would make Split a bit bigger (since you call it 3 times), but avoiding the call/ret instructions can make things even faster. That's a judgement call.

I realize I've only covered the first routine, but this answer is already 5 pages long. That seems like enough to get you started.

Main takeaways should be:

• Either remove stack frames, or document why they are needed.
• Decide what calling convention to use. They each have benefits (preserve all registers, faster, callable from C, etc), so decide what is important to your program.
• Consider inlining smaller routines.

While Cody never responded to my request for clarification, he does tend to be right about these things.

Still, I'm not going to remove the xchg from this answer. Why? Because making this routine small makes you start thinking about inlining it. And once you think about inlining it, you look again at this code:

mov dh,[byte ptr bx]
cmp dh,[byte ptr di]
jae greater
push ax;offset to be swapped
push bx;offset to be swapped
call Swap


So before calling Swap, we not only had the pointers, we also had the values and knew they needed to be swapped. Instead of pushing the pointers, preserving registers, re-loading the pointers re-reading the values, and restoring the registers, we could simply have written the swapped values:

mov dh,[byte ptr bx]   ; Read the first value
mov dl,[byte ptr di]   ; Read the second value
cmp dh, dl
jae greater            ; Are they correctly ordered?
mov [byte ptr bx], dl  ; Nope.  Swap them.
mov [byte ptr di], dh


So the question of how expensive xchg is drops out of the question. It was useful as a step along the way, even if ultimately it doesn't get used.

BTW, using a Swap routine in a higher-level language like C still makes sense. The C compiler can optimize this code and does the inlining for you. That way you get the benefit of clearer code (breaking out the Swap function makes the intent clear) while still getting the best performance.

Since assemblers aren't going "optimize" or "inline" for us, we as assembler programmers have to decide for ourselves where to make the trade-off between discrete functions and performance.

• Why would you use xchg? It saves you one register, but it's considerably slower. Register pressure is not an issue here, so I see no advantage of xchg. Apr 27, 2017 at 10:56
• How slow? In this case, a single xchg replaces 4 memory referencing instructions (push, pop plus 2 movs). The implicit lock on xchg has a penalty, but is it that big? Apr 27, 2017 at 22:55
• "I'm using the Microsoft Fastcall standard for 32bit code." Does your assembler then allow memory operands like [cx] [dx] [sp+2] ... Don't you need to write [ecx] [edx] [esp+2] ... ? Apr 29, 2017 at 12:56
• @Fifoernik I'm just using the 'standard' from 32bit code, which describe how registers are used. There are a number of things that would have to change to make this actually 32bit (ie esp+4). Apr 29, 2017 at 23:51