How does this 8086 code of ascending-sort work?

Question

I am currently learning 8086 programming and this one was demonstrated in our lab on a 8086 kit. The following code sorts sequence of numbers to ascending order:

mov si, 2000
mov cl, [si]
dec cl
loop1: mov si, 2000
       mov ch, [si]
       dec ch
       inc si
       loop2: mov al, [si]
              inc si
              cmp al, [si]
              
              jc loop3

              xchg al, [si]
              dec si
              xchg di, [si]
              inc si

       loop3: dec ch
              jnz loop2
       dec cl
       jnz loop1
int a5

How exactly does this function?

Say we have an array of N numbers d1, d2, ..., dN as follows:

Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
        |si  |

cl <-- [si]
{cl:N --> N-1}

LOOP 1:

ch <-- [si]
{ch:N --> N-1}
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
             |si  |

LOOP 2:

al <-- [si] = d1
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
                  |si  |
Compare [si] = d2 with al = d1.
If d1 > d2, jump to LOOP 3,
else d1 <= d2 and exchange d1 in al with d2 at si = 2002.
al = d2
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d1  |d3  |...|dN    |...|
                  |si  |
si --> si - 1
[di] = d1 (at 2001) 

LOOP 3:

{ch:N-1 --> N-2}
If ch is not zero then jump to LOOP 2.
al <-- [si] = d2 and so on.

At this point I feel like I am losing track of how the code really works. So, how does this work? Am I missing something? The example demonstrated was:

Address |2000|2001|2002|2003|2004|2005|...|
Input   |5   |04  |03  |01  |00  |02  |...|
Output  |5   |00  |01  |02  |03  |04  |...|

Answer 1

The troubles in this ascending bubble sort

• There's definitely a typo in xchg di, [si]. It should be clear that the code does not use the di register anywhere else, so this particular exchange instruction is useless. What would make sense is xchg al, [si], but even better would be a simple mov [si], al.
• Apart from bubble sort being the worst sorting method, here they made it extra bad by not acknowledging the most prominent feature of bubble sort which is 'make the max element bubble to the top of the array'. Once the max element has reached the top position, the code should no longer consider that top position and the next iteration should already stop one position earlier.

At this point I feel like I am losing track of how the code really works. So, how does this work? Am I missing something?

You are mis-interpreting the conditional jump in:

cmp al, [si]      <<<< AL = d1, [si], d2
jc loop3

when you state:

If d1 > d2, jump to LOOP 3,
else d1 <= d2 and exchange d1 in al with d2 at si = 2002.

The jc instruction should have been written as jb that has exactly the same encoding but that better conveys what it does: "If AL is below the byte at [si] then jump to LOOP3". So if d1 < d2 which is just the opposite of what you stated ("if d1 > d2").
Incidently, LOOP3 is a really bad name for this label! A more suitable name could be SKIP.

I would be so grateful if you could post a better-version of this code that is easy to understand.

       mov  si, 2000  ; Where the count resides
       mov  cl, [si]  ; CL is number of elements
       dec  cl        ; CL is number of iterations outer loop
Outer: mov  si, 2001  ; Where the first element resides
       mov  ch, cl    ; Ever smaller number of iterations inner loop (*)
Inner: mov  al, [si]
       inc  si
       cmp  al, [si]  ; Compare two adjacent elements
       jb   Skip      ; Skip the Swap if ordered fine already
Swap:  xchg al, [si]
       mov  [si-1], al
Skip:  dec  ch
       jnz  Inner     ; Iterate on the Inner loop
       dec  cl
       jnz  Outer     ; Iterate on the Outer loop

(*) This is the magic that makes bubble sort somewhat acceptable as a sorting method for small arrays!

More about writing a bubble sort code can be found at Sort 10 integer numbers read from keyboard and display in ascending order.