Bubble Sort in MASM x86 Not Sorting After Few Interations

Question

So, I am trying to implement BubbleSort, using this code as template:

    int n = arr.length;  
    int temp = 0;  
     for(int i=0; i < n; i++){  
             for(int j=1; j < (n-i); j++){  
                      if(arr[j-1] > arr[j]){  
                             //swap elements  
                             temp = arr[j-1];  
                             arr[j-1] = arr[j];  
                             arr[j] = temp;  

However, my assembly code only sorts the first 1 - 2 times and the produces an erroneous result. I tried running the debugger, stepping through multiple times, but my naive eyes could not spot any mistakes in the translation.

.data
arr DWORD 3,2,1,4,5
temp DWORD 0
arr_j DWORD 0
; Bubble Sort
.code
main proc
mov esi, OFFSET arr
mov eax, 0 ; for outer loop
mov ebx, 1 ; for inner loop

OuterLoop:

     InnerLoop:

        ; swap elements
        ; referencing j in array
        call MULTIPLY
        add edx, esi ; edx = esi + 4*ebx that is *arr[j]
        mov edi, [edx]
        mov [arr_j], edi ; store arr[j]
        sub edx, 4
        mov edi, [edx] ; store arr[j - 1]

        cmp edi, [arr_j] ; if(arr[j-1] > arr[j]) -> swap elements
        jle FAIL_SWAP

        ; swap elements here
        mov [temp], edi
        mov edi, [arr_j]
        mov ebp, [temp]
        mov [edx], edi ; arr[j - 1] < arr[j]
        add edx, 4
        mov [edx], ebp

        FAIL_SWAP:

     inc ebx
     mov ecx, LENGTHOF arr
     sub ecx, eax
     cmp ebx, ecx
     jl InnerLoop

inc eax
cmp eax, LENGTHOF arr
jl OuterLoop     


invoke ExitProcess,0
main ENDP

MULTIPLY PROC ; multiply 4 with ebx, store at edx
    push esi

    xor esi, esi
    mov esi, 1

    mov edx, ebx

    LOOPER:
    add edx, ebx

    inc esi
    cmp esi, 4
    jl LOOPER

    pop esi
    ret
MULTIPLY ENDP
END main

Any help is really appreciated. Thanks.

Answer 1

int n = arr.length;  
  int temp = 0;  
    for(int i=0; i < n; i++){  
      for(int j=1; j < (n-i); j++){
        ...

This template code already has an error. The outer loop does 1 iteration too many!
Consider a 2-element array where n is 2. The complete bubblesort will consist of a single comparison, yet the outer loop will do 2 iterations (i=0 and i=1). Clearly wrong.

mov eax, 0 ; for outer loop
mov ebx, 1 ; for inner loop
OuterLoop:
    InnerLoop:

The 1st time that your InnerLoop runs all is well, but the 2nd time it starts with BX=5 because that's the value BX got at the end of the loop. You need to reset the BX register to 1 every time the InnerLoop starts running.

mov eax, 0 ; for outer loop
OuterLoop:
    mov ebx, 1 ; for inner loop
    InnerLoop:

A simpler solution uses EAX as a decrementing counter:

mov eax, LENGTHOF arr
dec eax
OuterLoop:
    mov ebx, 1 ; for inner loop
    InnerLoop:
        ...
        inc ebx
        cmp ebx, eax
        jbe InnerLoop
    dec eax
    jnz OuterLoop

These will be the values for AX and BX for a 5 element array:

AX   BX
4    1 to 4
3    1 to 3
2    1 to 2
1    1 to 1

The rest of the code although correct, is overcomplicated and inefficient. See the comments by Peter Cordes.