# How do I optimize the bubble sort in Assembly8086?

I tried to implement bubble sort in Assembly 8086.

datasg      SEGMENT BYTE 'data'
array       DB 1, 3, 2, 5, 4
n           DW 5
datasg      ENDS
stacksg     SEGMENT BYTE STACK 'stack'
DW 12 DUP(?)
stacksg     ENDS
codesg      SEGMENT PARA 'code'
ASSUME CS:codesg, DS:datasg, SS:stacksg
MAIN        PROC FAR

; Pushing the previous data segment to keep it secure.
PUSH DS
XOR AX, AX
PUSH AX
MOV AX, datasg
MOV DS, AX
;SI = i
XOR SI, SI
MOV CX, n
DEC CX
out:        PUSH CX; Pushing CX to the stack before entering the second for loop
XOR DI, DI
MOV CX, n
DEC CX
SUB CX, SI
in:         MOV AH, array[DI]
CMP AH, array[DI+1]
JLE if_end
XCHG AH, array[DI+1]
MOV array[DI], AH
if_end:     INC DI
LOOP in
POP CX
INC SI
LOOP out
XOR SI, SI
; Some garbage code to move array elements to AL register one by one to see them while debugging.
MOV AL, array[SI]
INC SI
MOV AL, array[SI]
INC SI
MOV AL, array[SI]
INC SI
MOV AL, array[SI]
INC SI
MOV AL, array[SI]
RETF
MAIN        ENDP
codesg      ENDS
END MAIN


It seems to be working for the given example in the above code. I also tried it with different arrays and they all seem to work. I just want to learn if there is a way to improve it? Improvements like changing JMP codes to decrease the size of code or using AX with XCHG because that is faster.

I also can't comprehend the idea of pushing CX to stack for using nested-for loops. If you would give some suggestion about it I would be very happy.

• Great, but also drop bubble sort. If you're attempting a low-level, optimised implementation, best to use an algorithm that doesn't have implicit glaring performance issues. – Reinderien Nov 19 at 22:52

• On your array that has 5 elements
the 1st iteration of the outerloop (CX=4) has to do 4 compares in the innerloop
the 2nd iteration of the outerloop (CX=3) has to do 3 compares in the innerloop
the 3rd iteration of the outerloop (CX=2) has to do 2 compares in the innerloop
the 4th iteration of the outerloop (CX=1) has to do 1 compare in the innerloop

In your code you have initialized the outerloop counter correctly but you should see that the current value of the outerloop counter can serve as the initial value of the innerloop counter. You don't need to re-compute this!

• When it comes to speed, XCHG with a memory operand is bad. Normally we would load 2 successive elements in 2 different registers, compare those, and if necessary write them back switched.
However because your array contains byte-sized elements, you can load 2 elements in 1 word-sized register, compare its low and high byte-sized halves, and if necessary xchg the halves and write the word register back. That's how I did it in below code.

• The LOOP instruction has become infamous for being slow these days. You can easily replace it by the pair of instructions dec cx jnz ....

    mov   cx, n
dec   cx             ; Max number of compares is (n - 1)
outerloop:
push  cx             ; (1) Preserve outerloop counter CX

xor   di, di
innerloop:
mov   ax, array[di]
cmp   al, ah
jle   if_end
xchg  al, ah
mov   array[di], ax
if_end:
inc   di
dec   cx
jnz   innerloop

pop   cx             ; (1) Restore outerloop counter CX
dec   cx
jnz   outerloop


I also can't comprehend the idea of pushing CX to stack for using nested-for loops. If you would give some suggestion about it I would be very happy.

Pushing the outerloop counter CX is only necessary if the innerloop wants to use and change the CX register for its own purposes. We can easily re-write the above code and use e.g. BX to control the innerloop. Then we don't need to push cx or pop cx.

    mov   cx, n
dec   cx             ; Max number of compares is (n - 1)
outerloop:

mov   bx, cx
xor   di, di
innerloop:
mov   ax, array[di]
cmp   al, ah
jle   if_end
xchg  al, ah
mov   array[di], ax
if_end:
inc   di
dec   bx
jnz   innerloop

dec   cx
jnz   outerloop


And while we're optimizing this, we can even write the innerloop without using a special loop counter. We can use the index register DI at the same time for indexing the memory and for counting. This method also speeds things up since the combo cmp di, cx jb innerloop can macro-fuse and give us some extra speed.

    mov   cx, n
dec   cx             ; Max number of compares is (n - 1)
outerloop:

xor   di, di
innerloop:
mov   ax, array[di]
cmp   al, ah
jle   if_end
xchg  al, ah
mov   array[di], ax
if_end:
inc   di
cmp   di, cx
jb    innerloop

dec   cx
jnz   outerloop


stacksg     SEGMENT BYTE STACK 'stack'
DW 12 DUP(?)
stacksg     ENDS


Might I further suggest you set the stack to a more realistic value like 128 words?