Sort a List Using Recursive Merge Sort in X86 Assembly

Instructions

Objective

Write a program to sort a list using recursive merge sort in x86 Assembly language.

Requirements and Specifications

Description:

Write an x86 assembler assignment that to perform a recursive Mergesort sorting algorithm on a list of unsigned integers (up to 32-bits). The algorithm must correctly sort all the items in the input list in ascending order.

The declaration for the unsorted list must appear like the below picture in your code. Do not prompt the user to manually input the list.

Keep the following things in mind:

Be sure to reuse your for merging sorted lists from code from PA #5. If your PA#5 implementation did not work, then fix it before attempting this problem.
You must implement a recursive Merge Sort algorithm. The pseudocode for this, as well as other information on Mergesort, can be found in the attached PPT file. You can also Google other material and tutorials on Mergesort.
Do not artificially limit the size of the input list. Thus, you are advised to use operators to determine the size of the list.
Be aware that I will inspect your code as well as run it. If you implement an algorithm other than Mergesort (like Bubblesort), you will receive a zero. Your Mergesort implementation needs to be recursive.

Screenshots of output

sort a list using recursion in assembly language

sort a list using recursion in assembly language 1

sort a list using recursion in assembly language 2

sort a list using recursion in assembly language 3

sort a list using recursion in assembly language 4

Source Code

TITLE Program 7
; This program takes an unsorted array and sorts
; it using mergesort.
INCLUDE Irvine32.inc
.data
ProgInfo BYTE "CPSC 232 - Mergesort Program", 0
unSortList DWORD 1000, 501, 100, 51, 0, 1, 1, 0, 50, 101, 500, 1001
;unSortList DWORD 0,1,0,1,0,0,0,1,1,1,0,1,0
;unSortList DWORD 27,10,12,20,25,13,44,15,22,10,44,50,10
;unSortList DWORD 27,1000,12,20,25,13,44,15,22,10,44,50,10
;unSortList DWORD 100,99,98,97,96,95,94,93,92,91,90,50,51,52,53,54,55,56,57,59,59,10,9,8,7,6,5,4,3,2,1,0
tempList DWORD (LENGTHOF unsortList) DUP(0)
List1 BYTE "The unsorted list is: ", 0
List2 BYTE 10,"The sorted list is: ", 0
comma BYTE ", "
.code
Display PROC
 mov eax,[esi]
 add esi, 4
 call writedec
 dec ecx
DisplayLoop:
 lea edx, comma
 call writestring
 mov eax,[esi]
 add esi, 4
 call writedec
 loop DisplayLoop
 ret
Display ENDP
Merge proc
L1:
 cmp ebx, 0
 je AddArray2
 cmp ecx, 0
 je AddArray1
 mov eax,[esi]
 cmp eax,[edi]
 jl AddArray1 ;Jump if less
 jmp AddArray2 ;Jump if greater or equal
AddArray1:
 cmp ebx, 0
 je EndJump
 mov eax,[esi]
 mov [edx],ax
 add esi,4
 add edx,4
 dec ebx
 jmp L1
AddArray2:
 cmp ecx, 0
 je EndJump
 mov eax,[edi]
 mov [edx],ax
 add edi,4
 add edx,4
 dec ecx
 jmp L1
 EndJump:
 ret
Merge ENDP
; Sorts using mergesort,
; requires esi = array to sort, edi = temporary array, ecx = array length
 MergeSort PROC
 push ecx ; save length
 push esi ; save array
 push edi ; save temp array
 cmp ecx, 1 ; if length is 1, it's sorted
 jle endSort
 push ecx
 shr ecx,1 ; divide length by 2
 call MergeSort ; sort the half array
 mov eax, ecx
 pop ecx
 push esi
 push eax
 sub ecx, eax ; get length of second half of array
 shl eax, 2 ; multiply first array length by 4
 add esi, eax ; advance pointer
 call MergeSort ; sort the half array
 mov edx, edi
 mov edi, esi
 pop ebx ; load length of first array
 pop esi ; load address of first array
 call Merge
 mov esi,[esp] ; load address of temp array
 mov edi,[esp + 4] ; load address of initial array
 mov ecx, [esp+8] ; load number of elements
 ; copy from temp to initial array
copy:
 mov eax,[esi]
 mov [edi], eax
 add esi, 4
 add edi, 4
 loop copy
endSort:
 pop edi ; restore registers
 pop esi
 pop ecx
 ret
MergeSort ENDP
main PROC
 mov edx, OFFSET Proginfo
 call WriteString
 call Crlf
 call Crlf
 mov edx, offset List1
 call writestring
 mov ecx,lengthof unsortList
 mov esi,offset unsortList
 call Display
 mov esi,OFFSET unsortList
 mov edi,OFFSET tempList
 mov ecx,LENGTHOF unsortList ; elements in list
 call MergeSort
 mov edx, offset List2
 call writestring
 mov ecx,lengthof unsortList
 mov esi,offset unsortList
 call Display
 call Crlf
 exit
 main ENDP
 END main

Create a Program to Sort a List Using Recursive Merge Sort in X86 Assembly Language Assignment Solution.

Instructions

Requirements and Specifications