Instructions
Objective
Write a program to create a program to merge sort using recursion assembly language.
Requirements and Specifications
Description:
Write an x86 assembler assignment program 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 to implement a recursive Mergesort algorithm. The pseudocode for this, as well as other information on Mergesort, can be found in the attached PPNT 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
Source Code
TITLE CPSC 232 - Program #7
INCLUDE Irvine32.inc
.data
initialMsg DB "CPSC 232 - Mergesort Program", 0
unsortedMsg DB "The unsorted list is: ", 0
sortedMsg DB "The sorted list is: ", 0
comma DB ", ", 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 100 DUP(0)
.code
; Print the list in EDI with ECX dword elements
printList PROC
printLoop:
mov eax, [edi] ; load element from array
call WriteDec ; print the number
cmp ecx, 1 ; if it's the last element to print
je next ; if last, don't print the comma
mov edx, OFFSET comma ; load the comma string address
call WriteString ; print the comma
next:
add edi, 4 ; advance to next element
loop printLoop ; repeat for all numbers in list
call CRLF
ret
printList ENDP
; Merge two lists, ESI = first list, EDI = second list
; ECX = first list length, EDX = second list length
; saves result in list pointed by EBX
mergeLists PROC
enter 0, 0
pushad
loop1:
cmp ecx, 0 ; see if there are elements in first array
je copySecond ; if not, copy second array
cmp edx, 0 ; see if there are elements in second array
je copyFirst ; if not, copy first array
mov eax, [esi] ; load element from first array
cmp eax, [edi] ; compare with element in second array
jg save2 ; if first > second, save second
add esi, 4 ; advance to next element in first array
dec ecx ; decrement number of elements in first array
jmp saveElem ; save element in result array
save2:
mov eax, [edi] ; load element from second array
add edi, 4 ; advance to next element in second array
dec edx ; decrement number of elements in second array
saveElem:
mov [ebx], eax ; save element in array
add ebx, 4 ; advance to next element in temp array
jmp loop1 ; keep copying elements
copyFirst:
mov eax, [esi] ; load element from first array
mov [ebx], eax ; save element in array
add esi, 4 ; advance to next element in first array
add ebx, 4 ; advance to next element in temp array
dec ecx ; decrement number of elements in first array
jne copyFirst ; repeat until number in first array is zero
jmp mergeEnd ; end merge
copySecond:
mov eax, [edi] ; load element from second array
mov [ebx], eax ; save element in array
add edi, 4 ; advance to next element in first array
add ebx, 4 ; advance to next element in temp array
dec edx ; decrement number of elements in second array
jne copySecond ; repeat until number in second array is zero
mergeEnd:
popad
leave
ret
mergeLists ENDP
; Sort list recursively using mergesort
; The list is in EDI, the number of elements in ECX, the temporary
; list is in EBX
mergeSort PROC
enter 0, 0
pushad
cmp ecx, 1 ; see if length is 1
je sortEnd ; is 1, we don't need to sort
mov edx, ecx ; save length in edx
mov esi, edi ; save list pointer in esi
shr ecx, 1 ; divide length by 2
call mergeSort ; sort first part
mov eax, ecx ; copy first part length
shl eax, 2 ; multiply first part length by 4
add edi, eax ; add to start of list to get start of second half
mov eax, edx ; copy initial length
sub eax, ecx ; get rest of list
mov ecx, eax ; use as length to sort
call mergeSort ; sort second part
xchg edx, ecx ; get second length
shr ecx, 1 ; get first length
call mergeLists ; merge the two sorted lists
; copy merged list to initial
add ecx, edx ; add lengths to get merged list length
copyMerged:
mov eax, [ebx] ; load value from merged array
mov [esi], eax ; save in initial array
add esi, 4 ; advabce to next element
add ebx, 4 ; advabce to next element
loop copyMerged ; loop until all elements are copied
sortEnd:
popad
leave
ret
mergeSort ENDP
main PROC
; print initial list
mov edx, OFFSET initialMsg ; load address of string
call WriteString ; print the message
call CRLF
call CRLF
; print unsorted list message
mov edx, OFFSET unsortedMsg ; load address of string
call WriteString ; print the message
; print list
mov edi, OFFSET unSortList ; load unsorted list address
mov ecx, LENGTHOF unSortList ; load length of list
call printList ; print the list
; sort list
mov edi, OFFSET unSortList ; load unsorted list address
mov ecx, LENGTHOF unSortList ; load length of list
mov ebx, OFFSET tempList ; load temporary list address
call mergeSort ; sort list
; print sorted list message
mov edx, OFFSET sortedMsg ; load address of string
call WriteString ; print the message
; print list
mov edi, OFFSET unSortList ; load unsorted list address
mov ecx, LENGTHOF unSortList ; load length of list
call printList ; print the list
exit ; end of program
main ENDPEND main