1

I'm new to assembly language but I'm still stuck on this assignment. I need help with Insertion Sort assembly language. I don't get the part array[j+1] := array[j] in assembly code.
My assignment is:

Write an assembly language program to sort an array (a) of byte (a = {7, 5, 2, 3, 6}) using the Insertion Sort algorithm. Please allocate the array size as size = 5 in memory.
The basic principle behind the insertion sort is simple: insert a new number into the sorted array in its proper place. To apply this algorithm, we start with an empty array. Then insert the first number. Now the array is in sorted order with just one element. Next insert the second number in its proper place. This results in a sorted array of size two. Repeat this process until all the numbers are inserted. The pseudocode for this algorithm, shown below, assumes that the array index starts with 0:

Insertion Sort (array, size)
for (i = 1; i < size −1; i + +) do
temp := array[i]
j := i −1
while ((temp < array[j]) and (j ≥0)) do
array[j + 1] := array[j]
j := j −1
end while
array[j + 1] := temp
end for

Here, index i points to the number to be inserted. The array to the left of i is in sorted order. The numbers to be inserted are the ones located at or to the right of index i. The next number to be inserted is at i.

Here is what I got:

 segment .data
array    db   7,5,2,3,6
size     db   5
Sorted   times 5 db 0



            segment .text
            global main
main:   
        mov rsi, [Sorted]
      ;  mov edx,[size]
        sub edx,4                    ; size -1 
        mov ecx,1                    ;for (i = 1;
        
        for: cmp edx,ecx              ; i< size - 1; i++)
             je  finish               ; i = 0 then exit
             movsx rbx, byte[array + rcx] ; temp = array[i]
             mov rax, rcx          ; j = i - 1           
             sub rax,1  
           while:                  ;while ( temp < array[j] && j >= 0)
             cmp rax,0             ; j >= 0?   
             jl end_while     
             cmp rbx,[array + rax] ; temp < array[j]?
             jae end_while
           next:                     
             mov  r8, [array + rax + 1] ;????
             mov  r9, [array + rax]     ;????
             mov  r8,r9          ; array[j+1] := array[j]
             mov rsi,r8
             dec rax             ; j = j -1 
             inc rcx
             jmp 
             
            end_while:
             mov [Sorted + rax -1] ,rbx  ; array[j + 1] = temp
             inc rcx         
             jmp for 
             
          
       
   finish:
Sep Roland
  • 33,889
  • 7
  • 43
  • 76
Taylor Y
  • 11
  • 1
  • `array[j+1] := array[j]` in a loop is just `memmove`, i.e. a load and a store to a different location. Also, `r8` and so on are 64-bit registers, but your array has 8-bit elements. So you're loading 8 bytes at once. Single-step your code with a debugger and look at register values and memory change. (And maybe do the same for a working C version) – Peter Cordes Mar 03 '22 at 12:38

1 Answers1

1

The pseudocode does an in-place insertion sort, whereas your assembly code chooses to put the sorted elements elsewhere (not modifying the original array). That's a valid choice but then the comparing of elements should be done in the sorted array and not like you are doing in the unsorted array!

There are a lot of errors in the assembly code.

  • What is mov rsi, [Sorted] supposed to do? In NASM that you are using, this will load 8 bytes from memory. Perhaps you meant to load the address of the sorted array and then it would have to be mov rsi, Sorted or lea rsi, [Sorted]. (Or even RIP-relative...)

  • If you keep the comment sign in ; mov edx,[size] there's no hope to establish the correct iteration count.

  • The very first time that you fetch an element from the source array, you are using ECX=1. That might be fine is some high level language, but in assembly we use an offset into an array (and always count in bytes). You should have initialized ECX=0.

  • Because your array contains byte-sized elements, an instruction like cmp rbx,[array + rax] will be comparing 7 bytes too many! Just use cmp bl, ....

  • Similarly, mov [Sorted + rax -1] ,rbx ; array[j + 1] = temp will be overwriting 8 bytes where you should only be inserting a single byte. Also let's consider it a typo, but rax - 1 should really be rax + 1 in accordance with the comment that follows.

The basic principle behind the insertion sort is simple: insert a new number into the sorted array in its proper place. To apply this algorithm, we start with an empty array. Then insert the first number. Now the array is in sorted order with just one element. Next insert the second number in its proper place. This results in a sorted array of size two. Repeat this process until all the numbers are inserted. The pseudocode for this algorithm, shown below, assumes that the array index starts with 0

This is my version of this insertion sort. I did not follow the pseudocode at all. I studied the very clear explanation that was provided in the task description and wrote this solution solely based on that. Versions of the code in some high level language are certainly useful in trying to understand the task at hand, but IMO closely translating the high level code to assembly is a step in the wrong direction. You got to think in assembly. That's no different from how you learn a foreign language...

    xor ecx, ecx                   ; i := 0
.Top:
    mov bl, [Array + rcx]          ; Array[i]
    mov edx, ecx                   ; j := i
.While:
    sub edx, 1                     ; j := j - 1
    jb  .EndWhile
    mov al, [Sorted + rdx]         ; AL := Sorted[j]
    cmp bl, al
    jae .EndWhile
    mov [Sorted + rdx + 1], al     ; Sorted[j + 1] := AL
    jmp .While
.EndWhile:
    mov [Sorted + rdx + 1], bl     ; Sorted[j + 1] := Array[i]
    inc ecx                        ; i := i + 1
    cmp ecx, 5
    jb  .Top
Sep Roland
  • 33,889
  • 7
  • 43
  • 76
  • Normally you'd want `movzx eax, byte [Sorted + rdx]` to [load a byte](https://stackoverflow.com/q/20727379/224132), avoiding a false dependency. (Storing a byte still uses `mov [Sorted + rdx + 1], al`, and comparing can use either `cmp ebx, eax` or `cmp bl, al` after zero-extending both 8-bit integers.) Of course there are other optimizations you chose not to do for simplicity, e.g. arranging both loops with a conditional branch at the bottom to avoid `jmp`. Or using MMX or SSE2 to [copy + search 4, 8, or 16 bytes at a time in the inner loop](https://stackoverflow.com/a/56017051/224132) :) – Peter Cordes Dec 21 '22 at 23:04