Sorting Numbers in 8086 Assembly: A Worked Example

Sorting is the classic first array algorithm, and bubble sort is the easiest to trace by hand. It works by repeatedly comparing neighbouring numbers and swapping any pair that is out of order. After enough passes, the smallest values have bubbled to the front. You should already be comfortable with arrays and strings and loops before this one. Emu8086 setup is in the install guide.

The idea, in one paragraph

Each pass walks the array from left to right, comparing each pair of neighbours. Whenever the left number is larger than the right one, the two are swapped. After one full pass, the largest number has reached the end. Repeating the pass for the remaining elements eventually leaves the whole array in ascending order. The code below uses four passes for a five-element array, which is more than strictly necessary but keeps the loop structure simple and easy to trace.

The complete program

Read the inner loop first: it compares the two bytes SI points at, swaps them if they are out of order, then moves SI on. The outer loop repeats that walk. CX is saved on the stack around the inner loop because both loops need CX; the stack handling is explained in full in the subroutines and stack tutorial.

ORG 100h

MOV CX, 4
outer_loop:
PUSH CX
LEA SI, arr
MOV CX, 4
inner_loop:
MOV AL, [SI]
MOV BL, [SI+1]
CMP AL, BL
JBE no_swap
MOV [SI], BL
MOV [SI+1], AL
no_swap:
INC SI
LOOP inner_loop
POP CX
LOOP outer_loop
RET

arr DB 5, 2, 8, 1, 9

Trace it by hand

Start: 5, 2, 8, 1, 9. First pass: 5 and 2 swap to 2, 5; 5 and 8 stay; 8 and 1 swap to 1, 8; 8 and 9 stay. After pass one the array is 2, 5, 1, 8, 9. Second pass gives 2, 1, 5, 8, 9. Third pass gives 1, 2, 5, 8, 9. The fourth pass changes nothing, which is how you know the array is sorted. You should see exactly those intermediate states if you set a breakpoint at the POP CX line and inspect memory after each pass.

What you should see at the end

After the program finishes, the five bytes at arr should read 1, 2, 5, 8, 9 in order. If the last element looks wrong, check the inner-loop count: with five elements there are four neighbouring pairs per pass, so the inner loop must run four times, not five. Running it five times reads one byte past the end of the array and can corrupt the byte that follows it.

Ways to break it on purpose

  • Change the array to 9, 8, 7, 6, 5 and trace the worst case: every pair swaps.
  • Change the array to an already-sorted list and confirm that no swaps happen but the passes still run.
  • Try a duplicate value, such as 3, 3, 1, and check that equal neighbours are left alone by the JBE test.

Next steps

Bubble sort uses the stack to protect CX; subroutines and the stack explain that mechanism properly. To revisit the basics, see arrays and strings. The opcode reference covers CMP and the conditional jumps, and the home page is the series index.

Similar Posts